Java Reference
In-Depth Information
We assume the list is stored in an array, A , from A[lo] to A[hi] . We can code the algorithm as a Java method as
follows:
public static void mergeSort(int[] A, int lo, int hi) {
if (lo < hi) { //list contains at least 2 elements
int mid = (lo + hi) / 2; //get the mid-point subscript
mergeSort(A, lo, mid); //sort first half
mergeSort(A, mid + 1, hi); //sort second half
merge(A, lo, mid, hi); //merge sorted halves
}
} //end mergeSort
This assumes that merge is available and the statement
merge(A, lo, mid, hi);
will merge the sorted pieces in A[lo..mid] and A[mid+1..hi] so that A[lo..hi] is sorted. We will show how to write
merge shortly.
But first, we show how mergeSort sorts the following list stored in an array, num :
The method will be called with this:
mergeSort(num, 0, 6);
In the method, num will be known as A , lo will be 0 , and hi will be 6 . From these, mid will be calculated as 3 , giving
rise to the following two calls:
mergeSort(A, 0, 3);
mergeSort(A, 4, 6);
Assuming that the first will sort A[0..3] and the second will sort A[4..6] , we will have the following result:
merge will merge the pieces to produce the following:
Search WWH ::




Custom Search