My Mergesort
The basic operation of any sort is the swap, where two values in the array get swapped, (hopefully) making progress to the correct sort order. So if we're using recursion, the base case would involve doing a swap. This would sort two values for us, and we can split the whole array into these small 2-element parts and sort each one individually at the deepest recursion level. Of course, that will not sort the whole array for us, but are we making progress for the global order?
Consider this example of 8-element array (sticking to power of 2 for simplicity): {5,7,8,4,6,5,3,2}. We can split it at the first level into {5,7,8,4} and {6,5,3,2}. Then further, e.g. in the left branch, to {5,7} and {8,4}. We can now sort these two parts, we get {5,7} and {4,8}. When we go up a level, the super-part {5,7,4,8} is still not sorted. However, since we know that the two halves are sorted, we only need to compare the respectively ordered cells between the two parts, i.e. the first element in first and second part, the second element in first and second part, etc. In our example, we compare 5 and 4, 7 and 8, swapping if necessary. This gives us {4,7,5,8}. Notice that the list is still not sorted. We still need to swap the inner 2 elements, giving us the final sorted list {4,5,7,8}. This is the merge part of the sort - we merged the sorted {5,7} and {4,8} into a sorted {4,5,7,8}.
Now can answer the question: was sorting the smallest sub-list necessary? If we did not sort {5,7} and {8,4} before merging the two lists, we merging on upper-level would not get us a sorted list. Starting from {5,7,8,4}, we compare 5 and 8, 7 and 4, giving us {5,4,8,7}. Comparing 4 and 8 doesn't change the order. The final list is not sorted, because 7 and 8 were not swapping at the deepest level.
Here is my implementation of this method:
private void swap(Integer[] a, int i, int j){
if(a[j] < a[i]){
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
private void merge(Integer[] a, int i, int n){
if(n == 1)
swap(a, i, i+1);
else{
for (int k = 0; k < n; k++)
swap(a, i+k, i+n+k);
int m = n-1;
merge(a, i+1, m);
}
}
private void mergeSort(Integer[] a, int i, int n){
if(n == 2){
swap(a, i, i+1);
}
else{
int m = n/2;
mergeSort(a, i, m);
mergeSort(a, i+m, m);
merge(a, i, m);
}
}
public static void main(String[] args) {
MergeSort ms = new MergeSort();
int n = 1024;
Integer a[] = new Integer[n];
Random r = new Random();
for (int i = 0; i < n; i++) {
a[i] = r.nextInt(Integer.MAX_VALUE);
}
Integer b[] = a.clone();
Integer c[] = a.clone();
ms.mergeSort(b, 0, a.length);
Arrays.sort(c);
System.out.print(Arrays.equals(b, c));
}
1) The code does not work with array sizes other than powers of 2
2) There is a stack overflow exception for large input, e.g. 2^20
The second problem can be remedied by setting the stack memory size to 8MB: -Xss8192k. The first requires some extra thought. When splitting the array in mergeSort(), we will need to take the ceiling of n/2 to make sure we keep the n even. We also need to make sure j does not go out of bounds in the swap() function (for right-most nodes on the right branch). The code works correctly with those modifications:
private void swap(Integer[] a, int i, int j){
if(j < a.length && a[j] < a[i]){
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
private void merge(Integer[] a, int i, int n){
if(n == 1)
swap(a, i, i+1);
else{
for (int k = 0; k < n; k++)
swap(a, i+k, i+n+k);
int m = n-1;
merge(a, i+1, m);
}
}
private void mergeSort(Integer[] a, int i, int n){
if(n == 2){
swap(a, i, i+1);
}
else{
int m = (int)Math.ceil((double)n/2);
mergeSort(a, i, m);
mergeSort(a, i+m, m);
merge(a, i, m);
}
}
n^2 running time of bubble sort.
Comparing Solutions
Now it's time to delve into the book and compare my solution with one provided there. I'm sure the actual mergesort algorithm will be much faster than mine. Let's see where exactly I went wrong.
Turns out that overall, the code structure and the idea I had was very close to the original algorithm. As I expected, the biggest problem was in the merge operation. Merging is done in O(n), with at most n/2 comparisons when merging two lists of overall size n. The lists are merged by continuously comparing the first element of each of two lists and building a new, sorted list (instead of doing all the swapping in-line). This obviously reduces the number of comparisons we need to do in order to merge two lists. Also, the number of required comparisons scales linearly, and not exponentially (as in my case).
Fixing My Solution
Let's try to fix my algorithm to run as efficiently as the original mergesort algorithm:
private void merge(int[] a, int i, int m, int n){
int[] temp = new int[n];
int j = i; //start index of left part
int k = i+m; //start index of right part
for (int l = 0; l < temp.length; l++) {
if(j < i+m){
if(k < i+n){
if(a[j] <= a[k])
temp[l] = a[j++]; //pick first from left
else
temp[l] = a[k++];
}
else
temp[l] = a[j++]; //pick first from left
}
else
temp[l] = a[k++]; //pick first from right
}
for (int l = 0; l < temp.length; l++)
a[i+l] = temp[l];
}
private void mergeSort(int[] a, int i, int n){
if(n == 1)
return;
else{
int m = n/2;
mergeSort(a, i, m);
mergeSort(a, i+m, n-m);
merge(a, i, m, n);
}
}
Evaluation
I've tested my solution against the Java built-in sort for input size 1 million and 10 million (with multiple Random attempts). My code ran correctly for all input, and took about 2.5 times longer than Java's sort (which must be using something like quicksort). This is still much much faster than my original version and consumes way less memory!
