Merge Sort using Java

Code :


import java.util.*;

public class Merge
{
static void simplemerge(int a[],int f,int s,int t)
{
int i,j,k,w;
int temp[] = new int[a.length];

i = f;
j = s;
k = -1;

while(i <= s-1 && j <= t)
{
if(a[i] < a[j])
{
k++;
temp[k] = a[i];
i++;
}
else
{
k++;
temp[k] = a[j];
j++;
}
}

//now copy remaining elements in temp array

if(i > s-1)
{
for(w = j; w <= t; w++)
{
k++;
temp[k] = a[w];
}
}
else
{
for(w = i; w <= s-1; w++)
{
k++;
temp[k] = a[w];
}
}

//copy temp array back in array a

for(w = 0; w <= k; w++)
a[f+w] = temp[w];

}//end of simplemerge

static void mergesort(int a[], int left, int right)
{
int mid;

if(left < right)
{
mid = (left+right)/2;
mergesort(a,left,mid);
mergesort(a,mid+1,right);
simplemerge(a,left,mid+1,right);
}
}

public static void main(String args[])
{
System.out.println("Enter number of elements you wish to sort : ");
Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

//declare array of n elements

int a[] = new int[n];
//scan array from 0 to n-1 locations
for(int i = 0; i <= n-1;i++)
{
System.out.print("\nEnter element " + (i+1) + " : ");
a[i] = sc.nextInt();
}

System.out.println("\nOriginal array : ");

for(int i=0;i<=n-1;i++)
System.out.print(a[i] + " ");

//sort the array

mergesort(a,0,n-1);

//print sorted array

System.out.println("\nSorted array : ");

for(int i=0;i<=n-1;i++)
System.out.print(a[i] + " ");

}

}



Output :


Enter number of elements you wish to sort :
5

Enter element 1 : 5

Enter element 2 : 4

Enter element 3 : 1

Enter element 4 : 2

Enter element 5 : 6

Original array :
5 4 1 2 6
Sorted array :
1 2 4 5 6