Merge Sort Algorithm

In merge sorting algorithm unsorted values are divided into two equal parts iteratively. Then merge both parts and sort it. Then again merge the next part and sort it. Do it iteratively until  the values are not in sorted order. In merge sorting the number of elements must be even. 

In merge sort split the array values in halves recursively until each half has only single  element. Merge the two 1/2 values together and sort the values. Do same steps iteratively until the values are not sorted. 

In comparison to Quicksort the divide part is simple in Mergesort while the merging take is complex.
Quicksort can sort "inline" of an existing collection, e.g. it does not have to create a copy of the collection while Mergesort requires a copy. 

Example:

 12,9,4,99,120,1,3,10
 


public class mergeSort{
  public static void main(String a[]){
     int i;
     int array[] = {12,9,4,99,120,1,3,10};
     mergeSort_srt(array,0, array.length-1);
  }
  public static void mergeSort_srt(int array[],int lo, int n){
     int low = lo;
     int high = n;
     if(low >= high) {
        return;
     }
     int middle = (low + high) / 2;
     mergeSort_srt(array, low, middle);
     mergeSort_srt(array, middle + 1, high);
     int end_low = middle;
     int start_high = middle + 1;
     while((lo <= end_low) && (start_high <= high)) {
         if(array[low] < array[start_high]) {
            low++;
         }else {
            int Temp = array[start_high];
            for(int k = start_high- 1; k >= low; k--) {
               array[k+1] = array[k];
            }   
            array[low] = Temp;
            low++;
            end_low++;
            start_high++;
         }
     }
  }
}

Reference: roseindia