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