The following code snippet is from the book Algorithms by Robert SedgeWick and Kevin Wayne.
public class MergeBU {
// This class should not be instantiated.
private MergeBU() { }
// stably merge a[lo..mid] with a[mid+1..hi] using aux[lo..hi]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++]; // this copying is unneccessary
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
int n = a.length;
Comparable[] aux = new Comparable[n];
for (int len = 1; len < n; len *= 2) {
for (int lo = 0; lo < n-len; lo += len+len) {
int mid = lo+len-1;
int hi = Math.min(lo+len+len-1, n-1);
merge(a, aux, lo, mid, hi);
}
}
assert isSorted(a);
}
//other methods
}
My question is with respect to the inner for loop condition of the sort method.
In case the input array has 10 elements, the pass on the array that does a merge for subarrays of length 4 will leave the last two elements as is which are sorted with respect to each other but not with respect to the other elements.
In the next pass, the length of the subarray for the merge becomes 8 and it would still leave the last two elements unmerged with respect to the other elements. It's the last pass for the array of length 10.
So the last two elements remain unsorted with respect to the other elements in the array because of the lo < n-len check. This section doesn't say at any point that the number of elements in the array should be in the power of 2. Is this an errata or am I missing something?
I must definitely be overlooking something because the following test code sorts my 10 element array correctly.
public static void main(String[] args) {
Integer[] array = {1,2,3,4,5,6,7,8,-50, -80};
MergeBU.sort(array);
System.out.println(Arrays.toString(array));
}
Can someone help me figure it out.
Your analysis is incorrect. The merge proceeds as follows.
On the pass where len = 4, it will merge the two subarrays [0-3] and [4-7]. You are correct that the last two items are not merged.
When len = 8, it merges the two subarrays [0-7] and [8-9].
I suspect you're misunderstanding when the loop control variable gets incremented. You should single-step the sort method in the debugger, noting the values of lo and len in the two loops.
By the way, nothing in the definition of merge sort requires that the length be a power of two. Handling arrays that are not powers of two adds a little bit of complexity, though. That's why the if (i > mid) and if (j > hi) conditionals in the merge loop.