Recursion III: Divide and Conquer, and Mergesort

I now feel that it's time to tackle more advanced applications of recursion, especially those that are used in real-world algorithms - such as mergesort. At this point, I only vaguely remember how mergesort works, apart from the fact that it uses the recursive divide-and-conquer technique. Before finally diving into my algorithms book, I want to try to make sorting work on my own - using recursion - and then compare it to the actual algorithms presented in the book.

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

The way I tested this code is by generating a random array of integers and then sorting the same array with the Java's provided sorted, comparing with my order in the end:

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

The code passes multiple runs, but there are several problems still:
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);  
           }  
      }  

The code takes a while to execute, even for a moderate sample size 30k. I have a feeling that there is some inefficiency, particularly in the merge method. For input size 1024 (with fixed Random seed), my method took almost 40 times longer than the Java's sort. Looking at the JProfiler results, we can see the problem:

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

First thing you might notice is that I'm now using primitive int type. I was curious if the Object wrapper would be significantly slower than the primitive type, and this page suggests using primitives in most situations. I double checked that primitive arrays are passed by reference (i.e. the reference to the array is passed by value, as Java is pass by reference for everything except non-array primitive types).

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!