**Mergesort** and **Quicksort** are two well-known sorting algorithms, familiar to both researchers and practitioners. Both are usually explained as examples of **divide and conquer**. Other than this fact, they are usually not seen to be very closely related. Let’s look at Mergesort and Quicksort in a somewhat unusual way that will make them appear as two sides of the same coin.

Suppose we want to sort a list of items \(a_1, a_2, \dots, a_n\).

In **Mergesort**, we split the list in two parts: \(L = a_1, \dots, a_{n/2}\), and \(R = a_{n/2+1}, \dots, a_n\). We recursively sort \(L\) and \(R\), then merge the two sorted lists to obtain the final, sorted output.

How do we sort \(L\) and \(R\) recursively? We split them further into equal parts (let’s assume for simplicity that \(n\) is a power of two, so this always works), until parts consist of single elements, which are trivially sorted.

So, at the bottom of the recursion tree, we have \(n\) singleton-lists, consisting of \(a_1, a_2, \dots, a_n\). Assuming that the splitting has happened “in place”, these items are still stored in their original order, “sorted *by their index*” \(1,2,\dots,n\).

See the following illustration.

The bottom-most line contains the elements in their original order, one in each “box”. As we come out of the recursion, we merge neighboring “boxes” in pairs, putting their elements in the correct order. So within each box, elements are sorted “*by value*“.

Observe that neighboring boxes in the same line are sorted “*by index*“, in the sense that their ordering preserves the original order: indices of elements in a box are smaller than indices in a box to the right. For example in the second line from the bottom, the first box will contain \(a_1, a_2\), the next box will contain \(a_3, a_4\), etc.

*This is Mergesort.*

Can we reverse the arrow of time and go from the top towards the bottom? That would mean that we start with a single list that is already sorted, which wouldn’t make sense.

We can’t just assume that the input list is sorted, unless … unless, we mean “sorted *by index*“, meaning that the input is presented as \(a_1, a_2, \dots, a_n\). This is of course true, so there is no harm in assuming it. So let’s update the figure.

Instead of bottom-to-top, let’s go top-to-bottom. Let’s also swap “*by value*” and “*by index*” throughout.

So now we go from a single box, sorted *by index* (meaning an unsorted input list) to a list of boxes sorted among them *by value* (meaning a sorted output list). So conceptually, this looks very much like a valid sorting algorithm. What is it? Does it have a name?

**Yes, it is Quicksort.**

Let’s think it through again: we start with a list (sorted “by index”), and we produce from it two lists, sorted between them “by value”. This means that all entries in one are smaller than all entries in the other (this is essentially the partitioning step of Quicksort: we split the elements into those smaller, and those greater or equal than a *pivot*).

What does it mean that “within a box” the entries are now sorted “by index”? This just means that on both sides of the partitioning we preserve the original ordering of entries. This is not true in every implementation of Quicksort, but it is a technicality we can certainly enforce if we want to. Observe that we assumed that Quicksort splits the list in two *equal* parts, something we can achieve if we use the *median* as pivot (in practice of course a random pivot works just fine and is usually faster).

So there you have it. Quicksort and Mergesort are “duals”: you get one from the other by running time backwards, and swapping “by value” and “by index” in the invariants they maintain (or alternatively, swapping “between boxes” and “within boxes”).

Surprising? Obvious? Is this view of practical use?

What about other sorting algorithms?

For the latter question, observe that we can extend this view to accommodate unequal splits, or in an extreme case, just splitting off (or merging) one element from/to a longer list. In this view, we obtain (essentially) **InsertionSort**, respectively **SelectionSort**, which also appear as duals of each other.

This latter duality extends further, and holds even if we do insertion, resp. selection by fancy data structures, such as *self-adjusting binary search trees* and *adaptive tournaments* as heaps. These ideas are explored in a different direction in an article here.

There are also other dualities on ordered sets and data structures (the word itself is quite overloaded). Exploring dualities often suggests new concepts by symmetry or analogy.

As for the discussion of this post, here is an illustration of both sides.

## 0 comments ↓

There are no comments yet...Kick things off by filling out the form below.

## Leave a Comment