Merge Sort in JAVA

Introduction:

In today's article we discuss the Merge Sort using Java.

Merge Sort

The Merge Sort algorithm is based on a divide-and-conquer strategy. Merge Sorting was invented by John von Neumann in 1945. Its worst-case running time has a lower order of growth than an Insertion Sort. Here, we divide the array to be sorted into two halves, sort these two sub-arrays separately, and then combine (merge) these sorted sub-arrays to produce a solution to the original problem. For sorting the sub-arrays, we can use recursion. Since we are dealing with sub-problems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through sub-problems. In comparison to a Quicksort, the divide part is simple in a Merge Sort while the merging is complex. In addition a Quicksort can work "inline", for example it does not need to create a copy of the collection while a Merge Sort requires a copy.    

1. Divide Step

If a given array A has zero elements or one element then it simply returns; it is already sorted. Otherwise, partition the n-element sequence to be sorted into two subsequences of n/2 elements each.

2. Conquer Step

Sort the divided subsequences recursively using the Merge Sort.

3. Combine Step

Combine or merge the divided sorted subsequences, each to generate the sorted array consisting of n elements.

The following procedure shows how the data is sorted in a Merge Sort:

1.  If the list is of 1 in length, then the list is already sorted
2.  If the list size is more than 1, then divide the aray list into two parts. (An odd numbered length list can't be divided equally in two)
3. Continue to divide the sub-lists until we get a data size of 1 in length
4.  Now merge the divided-lists back into a list double their size, at the same time sorting each item into order
5.  Continue merging the divided lists until the full list is complete again

Advantages

1.  Stable performance
2.  It can be applied to files of any size
3.  Suited to sorting linked lists of elements because the merge traverses each linked list
4.  Suited to sorting external files; divides data into smaller files until can be stored in array in memory
5.  Conceptually simple

Example

public class MregeSortEx
 {
  public static void main(String a[])
   {
     //Numbers which are to be sorted
     int n[] = {124,23,43,12,177,25,2,1,67};
         //Displays the numbers before sorting
     System.out.print("Before sorting, numbers are ");
     for(int i = 0; i < n.length; i++)
      {
        System.out.print(n[i]+" ");
      }
     System.out.println();
         //Sorting in ascending order using bubble sort
     initializemergeSort(n,0,n.length-1);;
     //Displaying the numbers after sorting
     System.out.print("After sorting, numbers are ");
     for(int i = 0; i < n.length; i++)
      {
        System.out.print(n[i]+" ");
      }
     }
    //This method sorts the input array in asecnding order
   public static void initializemergeSort(int n[], int l, int h)
   {
     int low = l;
     int high = h;
     if (low>=high)
      {
        return;
      }
     int middle=(low+high)/2;
     initializemergeSort(n,low,middle);
     initializemergeSort(n,middle+1,high);
     int end_low=middle;
     int start_high=middle+1;
     while ((l<=end_low) && (start_high<=high))
      {
        if (n[low]<n[start_high])
         {
           low++;
         }
        else
         {
           int Temp=n[start_high];
           for (int k=start_high-1;k>=low;k--)
            {
              n[k+1]=n[k];
            }
           n[low]=Temp;
           low++;
           end_low++;
           start_high++;
         }
       }
    }  
 }

Output