## Java program to Sort a given set of n integer elements using Merge Sort method and compute its time complexity

				
import java.util.Random;
import java.util.Scanner;
public class mergesort {
static int max=10000;
void merge( int[] array,int low, int mid,int high)
{
int i=low;
int j=mid+1;
int k=low;
int[]resarray;
resarray=new int[max];
while(i<=mid&&j<=high)
{
if(array[i]
{
resarray[k]=array[i];
i++;
k++;
}
else
{
resarray[k]=array[j];
j++;
k++;
}
}
while(i<=mid)
resarray[k++]=array[i++];
while(j<=high)
resarray[k++]=array[j++];
for(int m=low;m<=high;m++)
array[m]=resarray[m];
}
void sort( int[] array,int low,int high)
{
if(low

{
int mid=(low+high)/2;
sort(array,low,mid);
sort(array,mid+1,high);
merge(array,low,mid,high);
}
}
public static void main(String[] args) {
int[] array;
int i;
System.out.println("Enter the array size");
Scanner sc =new Scanner(System.in);
int n=sc.nextInt();
array= new int[max];
Random generator=new Random();
for( i=0;i
array[i]=generator.nextInt(20);
System.out.println("Array before sorting");
for( i=0;i
System.out.println(array[i]+" ");
long startTime=System.nanoTime();
mergesort m=new mergesort();
m.sort(array,0,n-1);
long stopTime=System.nanoTime();
long elapseTime=(stopTime-startTime);
System.out.println("Time taken to sort array is:"+elapseTime+"nano
seconds");
System.out.println("Sorted array is");
for(i=0;i
System.out.println(array[i]);
}
}


Output:
Enter the array size
10
Array before sorting
13
9
13
16
13
3
0
6
4
5
Time taken to sort array is:171277nano seconds
Sorted array is
0 3 4 5 6 9 13 13 13 16