Our observation that we're forced to compare every element with every other element in the list in some cases is a consequence of how we work with our list. In other words, the idea that we've been relying on, that recursion follows naturally from the definition of our recursive data, is possibly hampering us. Indeed, if we think through the action of insertion sort, we'll see that we necessarily travel down the list linearly (i.e. how folds work).
This suggests that we may need to deviate from our approach, which HtDP calls structural recursion. But moving away from the structure of the data is fraught with danger. For instance, we have to be careful about how our recursive case progresses and to ensure that our base case is correct. We no longer have "obvious" approaches for both of these things.
We'll illustrate this non-structural approach, which HtDP calls generative recursion with two classic sorting algorithms. These are called generative because the recursion generates smaller subproblems to be solved. The results of these smaller solved subproblems are combined into a solution for the original problem. Both of the algorithms we'll see apply this via the divide-and-conquer paradigm of algorithm design.
The first is Quicksort, due to C.A.R. Hoare in 1959 and the second is Mergesort, due to John von Neumann in 1945. Both of these sorting algorithms are provably more efficient than insertion sort. They are also efficient empirically—both for the basis of default sorting implementations in almost all modern programming languages in some form.
Quicksort is due to C.A.R. Hoare in 1959. Hoare is most well-known for Quicksort as well as Hoare logic, which is a logic for program verfiication, and null pointers. Quicksort is used as a foundation for many default implementations of sorting in various programming languages, including C, Java, and C++.
The key observation behind Quicksort is the following. We can divide our list into two smaller lists relative to an arbitrary element in the list: everything that is less than it and everything that is greater than it. Recall that insertion sort takes the first element of the list and inserts it into the right place in the rest of the list, which is recursively sorted. Instead, Quicksort takes the first element of the list (the head, which we call the pivot) and rearranges the rest of the list (the tail) around the pivot.
For example, consider the list $(234,54,32,65,6785,6,283,309)$. We decompose our list into three parts: the pivot, 234; the list of elements less than our pivot; and the list of elements greater than our pivot. \[(54, 32, 65, 6) \quad 234 \quad (6785, 283, 309)\]
Of course, this is not sorted, but it's closer to being sorted. Note that if we then sort the two lists on either side of 234, 234 is already in the right place in relation to all of the other elements in the list! To sort the other lists, we repeat our approach recursively, pivoting elements around in the sublists.
This rearrangement generally accomplishes something very important: nothing to the left of our pivot ever gets compared to anything on the right of the pivot! If everything works out, we can avoid some number of comparisons in this way.
However, an issue is that this recursion doesn't quite follow the recursive structure of the list. To ensure that our recursion will terminate, we need to examine our base cases and recursive cases carefully. Luckily, the base case in this case is pretty simple: we just take the empty set.
Then all that's left is to observe that because each sublist is constructed on the basis of whether it an element is strictly less than or greater than the pivot, the sublists are necessarily smaller than the original list. Therefore, every level of recursion approaches the base case and we can guarantee termination.
So how do we "rearrange" our list in Racket? Suppose our first element is $p$. Then we need a list of elements that are less than $p$ and a list of elements that are greater than $p$. But this is something we've seen before: this is just all $x$ such that $x \lt p$. This is something that can be naturally written with a filter. If our list has the form (cons head tail), then we have
(filter (lambda ([x : Integer]) (< x head)) tail)and something similar for $\gt$. Let's give all of these things names. Let the list described above be the list less-than and let the corresponding list for elements greater than head be called greater-than. Then the result we would expect is a list
(append (sort less-than) (list head) (sort greater-than))Putting that all together, we get the following function.
(: quick-sort (-> (Listof Integer) (Listof Integer)))
;; Produce a sorted list of Integers
(define (quick-sort lst)
(match lst
['() '()]
[(cons pivot xs)
(local
{(define lt (filter (lambda ([x : Integer]) (< x pivot)) xs))
(define gt (filter (lambda ([x : Integer]) (> x pivot)) xs))}
(append (quick-sort lt) (list pivot) (quick-sort gt)))]))
There are a few questions that you might have after seeing this. One obvious thing that should make you raise an eyebrow is our choice of the first element of the list as the pivot. This is an issue because a careful observer would note that this algorithm doesn't actually avoid the bad case we discussed with insertion sort: we'd end up in exactly the same pickle.
From this, it seems like the best choice of pivot is when we can make these two lists about the same size. In other words, we need some way to pick the median element. But how would we do that? The answer to this question is surprisingly difficult, and wasn't solved until 1973.
In practice, what happens is this: a pivot is randomly chosen from the list elements with uniform probability. This is both empirically and theoretically provable (due to some probabilistic analysis that you may see in later courses) to be highly efficient.
The next algorithm we'll see is called Mergesort and is due to John von Neumann in 1945. Mergesort is used as a foundation for many default implementations of sorting in various programming languages, including Java and Python.
Recall that insertion sort relies on the idea that inserting a single element into a sorted list is a relatively straightforward task. Similarly, the key insight for Mergesort is that if we're given two sorted lists, we can very easily combine them into one sorted list.
So there are two pieces to this algorithm: first, we need to break our list up and handle the small cases; secondly, we need to be able to merge two sorted lists together.
Let's tackle the merging first. Suppose we have two lists that we know are sorted and we want to try to combine them into one sorted list. How do we do this? Well, it's actually not too hard. We know that both lists are sorted so the very first elements should be the smallest ones. So we can just repeatedly look at the front of the two lists, compare what we see, and put the right one in the right place while we build the new list.
For example, if we have the lists $(1, 3, 6, 9)$ and $(2, 4, 8, 16)$, then to put them in order, we first compare 1 and 2. We put 1 in our new list and then look at the next element, 3, and compare that with 2. We repeat this process.
Now, let's consider the main algorithm. The obvious approach here is to divide our list in half and then sort each half. The implication here is that "sort each half" really means "sort each half using Mergesort", which turns our algorithm into a recursive algorithm.
As we mentioned before, this differs from our usual approach of mirroring our function on the definition of the structure we're operating on, so we need to examine the base case and recursive cases carefully to ensure that our recursion will terminate.
First, let's consider the base case. An obvious base case is the empty list: the empty list is already sorted. But there's a second base case: lists containing a single element. This base case is necessary because we aren't able to treat it in the same way as our recursive case, as it's impossible to split a list with only one element into two. However, this case is easy to handle as well: a list containing a single element is already sorted.
Finally, we need to convince ourselves that this recursion will terminate. Luckily, this is not difficult to argue. We observe that we because we are always dividing our list into two, each of the two sublists is necessarily smaller. This means that with each step of recursion, we are always approaching the base cases.
With that, we can try writing our version of Mergesort.
(: merge-sort (-> (Listof Integer) (Listof Integer)))
;; Produce a sorted list of Integers
(define (merge-sort lst)
(match lst
['() '()]
[(cons head '()) lst]
[_
(local
{(define l (take lst (quotient (length lst) 2)))
(define r (drop lst (quotient (length lst) 2)))}
(merge (merge-sort l) (merge-sort r)))]))
An implementation note: here, we take the first half of our list (l for left) to be the first $\lfloor n/2 \rfloor$ elements of the list, and the remainder (r for right) as the second half. Then the recursive case is: sort these two lists using merge-sort and merge them.
But we still have one final piece of code to write: merge.