Merge Sort

The divide-and-conquer paradigm involves three steps at each level of the recursion:

Divide the problem into a number of subproblems that are smaller instances of the same problem.
Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
Combine the solutions to the subproblems into the solution for the original problem.

The merge sort algorithm closely follows the divide-and-conquer paradigm. [1]

The key operation of the merge sort algorithm is the merging of two sorted sequences in the “combine” step. We merge by calling an auxiliary procedure MERGE(A, p, q, r), where A is an array and p, q, and r are indices into the array such that $p ≤ q < r$. The procedure assumes that the subarrays A[p..q] and A[q+1..r] are in sorted order. It merges them to form a single sorted subarray that replaces the current subarray A[p..r]. Our MERGE procedure takes time $Θ(n)$, where $n = r - p + 1$ is the total number of elements being merged. [1]

Let's directly get into the chapter end exercise of the CLRS book [1] and try to solve that problem.

2.3-2
Rewrite the MERGE procedure so that it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A.

It's not that hard to write a merge procedure and a merge-sort routine which sorts an array of integers. Today our goal is to go beyond that and write a much more reusable function which allows us to sort literally anything that we may encounter.

Much has been written on generics, and their introduction into Java has sparked some controversy. Certainly, the design of generics involves swings and roundabouts, and in this article we are going to exploit their strengths and work around their weaknesses.

A complete treatment of the Merge Sort algorithm and it's analysis is beyond the scope of this article, but the interested reader is directed to Introduction to Algorithms. [1] I am not going to provide the algorithm and it's pseudo code, instead, going to focus on writing a much reusable library function for sorting a given sequence of objects using merge sort. 

Our API has two subroutines for sorting a sequence of objects. One method can be used to sort a sequence of objects in natural order whereas the other can be used to sort the objects in any  other arbitrary order. Since the algorithm is not that hard, let’s directly get into our library implementation for sorting. Here’s how it looks.

Now let’s use our library implementation to sort sequences of  objects. Our trivial scenario is just to sort an array of integers which is straightforward. Our non-trivial example is, given a sequence of students each with a name and gpa value, sort the students in descending order based on their gpa value, from the highest gpa to the lowest. We are interested in knowing the students with the highest gpa values first. 

Newton is reputed to have said, “If I have seen farther than others, it is because I stand on the shoulders of giants”. The best programmers live by this motto, building on existing frameworks and reusable code wherever appropriate. The Java library provides a convenience class called Arrays which provides a large set of API methods to sort arrays. So, even though we wrote a library for sorting a sequence of objects, I will recommend you against using this. Instead, use the Java library for sorting arrays. I just wanted to show you how to write such a library, leveraging the features of the language and it’s type system.

Analysis

Let’s use the master method to solve the recurrence for the Merge sort. $$T(n) = 2T(n/2) + Θ(n)$$ Here we have $a = 2,\quad b = 2,\quad f(n) = Θ(n)$, and thus we have that $n^{log_b a} = n^{log_2 2} = n$. Case 2 applies, since $f(n) = Θ(n)$, and so we have the solution $T(n) = Θ(n\ log_2\ n)$.

References

[1] https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844