Merge Sort

Merge sort runs in O(nlogn). It uses an divide and conquer. First, it divide the original array into two sub array until it has only 1 element in the array. Then, it merge the sub-arrays by sorting it in correct order.
The example will be more clear.
We have an integer array {7,5,9,10,1,6,13,2,8}, and by applying merge sort, we have the following sequences.

The code implemented in Java is in the below.


 import java.io.*;
 import java.util.Arrays;
 class myCode
 {
   public static void main (String[] args) throws java.lang.Exception
   {
     System.out.println("Hello Java");
     int[] input = {7,5,9,10,1,6,13,2,8};
     int[] output = mergeSort(input);
     System.out.println("sorted list:");
     for (int i=0;i<output.length;i++) {
       System.out.print(output[i] + ",");
     }
   }
   public static int[] mergeSort(int[] array) {
     int middle = array.length/2;
     if (array.length < 2) {
       return array;
     } else {
       int[] left = mergeSort(Arrays.copyOfRange(array, 0, middle));
       int[] right = mergeSort(Arrays.copyOfRange(array, middle, array.length));
       return merge(left,right);
     }
   }
   public static int[] merge(int[] a, int[] b) {
     int len = a.length + b.length;
     int[] result = new int[len];
     int i=0;
     int j=0;
     while (i<a.length || j<b.length) {
       if (j >= b.length || (i < a.length && a[i]<b[j])) {
         result[i+j] = a[i];
         i++;
       } else {
         result[i+j] = b[j];
         j++;
       }
     }
     return result;
   }
 }