Merge Sort in Java

Introduction
In this example we are going to sort integer values of an array using merge sort.

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. The merge sorting is invented by John von Neumann in 1945 .
The complexity of the merge sorting is in worst-case O(n log n) and in average case O(n log n).
  
Code description:
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.

Working of merge sort algorithm:
Say we have an array unsorted  A[0],A[1],A[2]................ A[n-1] and A[n] as input. Then the following steps are followed by merge sort algorithm to sort the values of an array.

Step1:Spliting the values of array
Divide the values into two equal 1/2
   A[0],A[1],A[2].........A[n/2-1]   &  A[n/2]....... .................A[n-1], A[n]

Again divide two equal 1/2
A[0] a[1]A[2]..............A[(n/2-1)/2-1] &  A[(n/2-1)/2]............A[n/2-1],
A[n/2].............A[(2n-1)/2-1]  & a[(2n-1)/2].............A[n-1],A[n]
..........................................................................................................................
..........................................................................................................................
........................................................................................................................
A[0] & A[1] & A[2]& A[3],..............................................................A[n-1]& A[n]

Step2:Merge two values  and sort the values

A[0],A[1] & A[2],A[3]&..................................................................&A[n-1],A[n]
If A[1]<A[0],A[]<A[3]........................................................................A[n-1]>A[n]
then
A[1]A[0],A[2]A[3],...............................................................................A[n]A[n-1]
Step3:Merge four values and sort the values
A[2] A[1] A[0] A[3],...................................................................................A[n-1]
..................................................................................................................
..................................................................................................................
.................................................................................................................
Step3:Merge n values and sort the values
A[2]A[6]......................................................................................................A[n-5]

Where n must be even number.

Steps of Merge Sort:

Say unsorted  an array values are:
12,9,4,99,120,1,3,10


The code of the program :

public class mergeSort{   public static void main(String a[]){   int i;   int array[] = {12,9,4,99,120,1,3,10};   System.out.println("\n\n RoseIndia\n\n");   System.out.println(" Selection Sort\n\n");   System.out.println("Values Before the sort:\n");   for(i = 0; i < array.length; i++)   System.out.print( array[i]+"  ");   System.out.println();   mergeSort_srt(array,0, array.length-1);   System.out.print("Values after the sort:\n");   for(i = 0; i <array.length; i++)   System.out.print(array[i]+"  ");   System.out.println();   System.out.println("PAUSE");   }   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++;   }   }   }   }

Output of the example:

C:\array\sorting>javac mergeSort.java C:\array\sorting>java mergeSort RoseIndia Selection Sort Values Before the sort: 12 9 4 99 120 1 3 10 Values after the sort: 1 3 4 9 10 12 99 120 PAUSE C:\array\sorting>_

Download this example.