About Merge Sort

Sorting is a common and important problem in computing. Given a sequence of N data elements, we are required to generate an ordered sequence that contains the same elements. Here, I present a Java version of the well-known mergesort algorithm.

The mergesort algorithm is as follows; its execution is illustrated as following:

1. If the input sequence has only one element, return.
2. Partition the input sequence into two halves.
3. Sort the two subsequences using the same algorithm.
4. Merge the two sorted subsequences to form the output sequence.
Here is the algorithm that is used in the merge sort java applet animation:

     void mergesort(int a[], int low, int high)  { 
       if(low == high)  
            return; 
       int length = high-low+1; 
       int pivot = (low+high) / 2; 
       mergesort(a, low, pivot); 
       mergesort(a, pivot+1, high); 
       int working[] = new int[length]; 
       for(int i = 0; i < length; i++)  
           working[i] = a[low+i]; 
       int m1 = 0;  
       int m2 = pivot-low+1; 
       for(int i = 0; i < length; i++) { 
         if(m2 <= high-low)  
             if(m1 <= pivot-low)  
                 if(working[m1] > working[m2])  
                     a[i+low] = working[m2++];   
                 else  
                     a[i+low] = working[m1++]; 
             else  
                 a[i+low] = working[m2++]; 
         else  
             a[i+low] = working[m1++]; 
       } 
     }

The merge operation employed in step (4) combines two sorted subsequences to produce a single sorted sequence. It repeatedly compares the heads of the two subsequences and outputs the lesser value until no elements remain. Mergesort requires time to sort N elements, which is the worst that can be achieved O(nlogn)(modulo constant factors) .