Merge Sort Java Program

1. import java.util.Scanner;
2.  
3. 
   
4. public class MergeSort 
5. {
6.     
7.     public static void sort(int[] a, int low, int high) 
8.     {
9.         int N = high - low;         
10.         if (N <= 1) 
11.             return; 
12.         int mid = low + N/2; 
13.         // recursively sort 
14.         sort(a, low, mid); 
15.         sort(a, mid, high); 
16.         // merging two sorted sub-arrays
17.         int[] temp = new int[N];
18.         int i = low, j = mid;
19.         for (int k = 0; k < N; k++) 
20.         {
21.             if (i == mid)  
22.                 temp[k] = a[j++];
23.             else if (j == high) 
24.                 temp[k] = a[i++];
25.             else if (a[j]<a[i]) 
26.                 temp[k] = a[j++];
27.             else 
28.                 temp[k] = a[i++];
29.         }    
30.         for (int k = 0; k < N; k++) 
31.             a[low + k] = temp[k];         
32.     }
33. 
    
34.     public static void main(String[] args) 
35.     {
36.         Scanner scan = new Scanner( System.in );        
37.         System.out.println("Merge Sort");
38.         int n, i;
39. 
    
40.         System.out.println("Enter number");
41.         n = scan.nextInt();
42.         int arr[] = new int[ n ];
43. 
    
44.         for (i = 0; i < n; i++)
45.             arr[i] = scan.nextInt();
46.         sort(arr, 0, n);
47. 
    
48.         System.out.println("Sorted element");        
49.         for (i = 0; i < n; i++)
50.             System.out.print(arr[i]+" ");            
51.         System.out.println();            
52.     }    
53. }

Merge sort time complexity

        Worst case performance : O(n log n)

        Best case performance : O(n log n)

        Average case performance : O(n log n)