Sorting in Java - Part 5

This is part 5 of the series. It is suggested to read the whole series from the beginning.

• Part 1
• Part 2
• Part 3
• Part 4

Simple Merge Sort Revisited

The simple merge sort described in the previous article allocate memory for holding the sub-lists inside the recursive function.



Under many platforms, memory allocation is expensive and sequential in nature. Hence allocating array inside recursive function would kill performance and concurrency. A better method is to allocate the memory in the initialization phase and pass the helper array as temporary storage.

The first modification is stop allocating memory for the sublists. Instead of using physical storage for the sublists, we divide the original array into two logical sublists. We accomplish this by first finding the mid point of the array index. For example, if the array contains 8 elements, then the mid point is

mid = n/2 = 8/2 = 4 

It follows that a[0] .. a[3] should be in the left sublist, and the element a[4] .. a[7] should be in the right sublist. Put it in a more precise way :

left sublist  = { a[0], a[1], ... a[mid-1] }
right sublist = { a[mid], a[mid+1], ..., a[n-1] }

For an array of 8 elements, we don't have to start with 0 and ends with 7. For example, we may want to sort the partial array a[2]..a[4]. Hence we can extend the above formula.

If we want to sort the partial array a[low]..a[high], then
mid = length / 2 = (high - low + 1) /2
left sublist  = { a[low], a[low+1], a[low+2], ... a[low+mid-1] }
right sublist = { a[low+mid], a[low+mid+1], a[low+mid+2], ... a[high] }

The above observation immediate leads to the following modification to the MergeSort algorithm.

/******************************************************************************
* File : HelperMergeSort.java
* Author : http://java.macteki.com/
* Description :
*   Implementation of Merge Sort with a helper array
* Tested with : JDK 1.6
******************************************************************************/

class HelperMergeSort
{

  public static void printArray(int[] a)
  {
    String delim="";
    for (int i=0;i<a.length;i++)
    {
      System.out.print(delim+a[i]);
      delim=",";   // add delimiter after first element
    }
    System.out.println();
  }

  

  public static void mergeSort(int[] a,int low,int high,int[] helper)
  {
    int length=high-low+1;
    if (length<=1) return;   // a list with only 1 element is already sorted
    int mid=length/2;    
    
    mergeSort(a,low,low+mid-1,helper);      // sort the left sub-list
    mergeSort(a,low+mid,high,helper);       // sort the right sub-list
    merge(a,low,high,helper);      // merge the sorted lists
  }

  // merge the left and right sublists into the helper array.
  // the sorted helper is then copied back to the original array a[].
  public static void merge(int[] a, int low,int high,int[] helper)
  {
    int mid=(high-low+1)/2;
    int ai=low,bi=low,ci=low+mid;

    while (ai<=high)
    {
      if (bi<=low+mid-1 && ci<=high)  // both lists contains element
      {
        // append the smaller one to the result.  
        helper[ai++]=(a[bi]<a[ci])?a[bi++]:a[ci++];
      }    
      else if (bi<=low+mid-1)    // only the left sub-list contains element
      {
        while (ai<=high) helper[ai++]=a[bi++];
      }
      else                      // only the right sub-list contains element
      {
        while (ai<=high) helper[ai++]=a[ci++];      
      }
    }

    // copied back the helper to the input array
    for (int i=low;i<=high;i++)
    {
      a[i]=helper[i];
    }
  }


  public static void main(String[] args) throws Exception
  {
    int[] a={86,29,29,20,91,78,73,13,98,85,90,19,98,66,12,41,36,33,19,94,27,49,
             23,97,94};

    int[] helper=new int[a.length];
    mergeSort(a,0,a.length-1,helper);    
    
    printArray(a);
  }
}

Next

We have removed the big concurrency killer with the helper array. We should go concurrent now. In the next section we will implement a concurrent merge sort that performs much better in multiprocessor environment.