//Merge sort implementation using java programming
import java.util.Scanner;
import java.util.Arrays;
class MergeSortPrac
{
public static void main(String args[])
{
Scanner s=new Scanner(System.in);
System.out.println("Enter a Integer Number :");
int length=s.nextInt();
int arr[]=new int[length];
for(int i=0; i<arr.length; i++)
{
arr[i]=s.nextInt();
}
MergeSortPrac obj=new MergeSortPrac();
obj.sort(arr,0,arr.length-1);
System.out.println("Sorted Data :"+Arrays.toString(arr));
}
private void sort(int arr[],int low, int high)
{
if(low>=high)
{
return;
}
int mid=(low+high)/2;
sort(arr,low,mid);
sort(arr,mid+1,high);
merge(arr,low,mid,high);
}
private void merge(int arr[],int low,int mid,int high)
{
int brr[]=new int[high+1];
int i=low;//for left partition
int j=mid+1;//for right partition
int k=0;//for brr
while(i<=mid && j<=high)
{
if(arr[i]<=arr[j])
{
brr[k]=arr[i];
k=k+1;
i=i+1;
}
else
{
brr[k]=arr[j];
k=k+1;
j=j+1;
}
}
if(i>mid)
{
//process j
while(j<=high)
{
brr[k]=arr[j];
k=k+1;
j=j+1;
}
}
else
{
//process i
while(i<=mid)
{
brr[k]=arr[i];
k=k+1;
i=i+1;
}
}
int p=0;
for(int x=low; x<=high; x++)
{
arr[x]=brr[p];
p=p+1;
}
}
}
Expected Output :
0 Comments