Merge-sort

There are three sorting algorithms:

• Merge-sort
• Quicksort
• Heap-sort

Each of these algorithms takes an input array a and sorts the elements of a into non-decreasing order in $O(n \log n)$ (expected) time. These algorithms are all comparison-based. These algorithms don’t care what type of data is being sorted, the only operation they do on the data is comparisons using the compare(a, b) method. Recall that compare(a, b) returns a negative value if $a < b$, a positive value if $a > b$, and zero if $a = b$.

This module discusses algorithms for sorting a set of n items. This might seem like a strange topic for a course on data structures, but there are several good reasons for including it here. The most obvious reason is that two of these sorting algorithms (quicksort and heap-sort) are intimately related to two of the data structures we have already studied (random binary search trees and heaps, respectively).

Basics of sorting

There are several algorithms that sort using only comparisons and they run in $O(n \log n)$ time. As it turns out, all three algorithms are asymptotically optimal; no algorithm that uses only comparisons can avoid doing roughly $n \log n$ comparisons in the worst case and even the average case.

Before continuing, we should note that any of the SSet or priority Queue implementations can also be used to obtain an $O(n \log n)$ time sorting algorithm. For example, we can sort n items by performing $n$ add(x) operations followed by $n$ remove() operations on a BinaryHeap or MeldableHeap. Alternatively, we can use $n$ add(x) operations on any of the binary search tree data structures and then perform an in-order traversal to extract the elements in sorted order. However, in both cases, we go through a lot of overhead to build a structure that is never fully used. Sorting is such an important problem that it is worthwhile developing direct methods that are as fast, simple, and space efficient as possible.

If we allow other operations besides comparisons, then all bets are off. Indeed, by using array indexing, it is possible to sort a set of $n$ integers in the range $\{0,...,n^c −1\}$ in $O(cn)$ time.

The merge-sort algorithm is a classic example of recursive divide and conquer: if the length of a is at most $1$, then a is already sorted, so we do nothing. Otherwise, we split a into two halves, a0 = a[0],...,a[n/2 − 1] and a1 = a[n/2],...,a[n − 1]. We recursively sort a0 and a1, and then we merge (the now sorted) a0 and a1 to get our fully sorted array a:

Visual demonstration

An example is shown below:

Compared to sorting, merging the two sorted arrays a0 and a1 is fairly easy. We add elements to a one at a time. If a0 or a1 is empty, then we add the next elements from the other (non-empty) array. Otherwise, we take the minimum of the next element in a0 and the next element in a1 and add it to a:

Notice that the merge(a0, a1, a) algorithm performs at most n − 1 comparisons before running out of elements in one of a0 or a1.

Running time of merge-sort

To understand the running time of merge-sort, it is easiest to think of it in terms of its recursion tree. Let’s suppose for now that $n$ is a power of two so that $n = 2^{\log n}$ ...