### 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 = 4It 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], thenThe above observation immediate leads to the following modification to the MergeSort algorithm.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] }

/****************************************************************************** * 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); } }

## No comments:

## Post a Comment