How to explain algorithms

Intuitive explanation of quick-sort as a case study of the value of live knowledge

Whenever I look at old ideas I like to form a view about what problems and context led to their creation. What were people trying to do? What sort of obstacles did they encounter that ultimately led to the idea that you now see before you?

In this regard I’ve always been a bit puzzled by sorting algorithms. Sorting is the problem of starting with a list of objects somewhere in memory and rearranging them in a sorted order. Books on algorithms typically contain a large number of different sorting algorithms. They usually start with simple algorithms and then progresses to ever more elaborate ones that, upon analysis, turn out to use fewer comparisons or swaps as earlier ones. But what led people to these procedures? For many of them it is not immediately apparent why they work better than earlier methods, nor what would lead you to consider them in the first place.

One such algorithm is quick-sort. Many years ago I came up with the explanation below that immediately made the algorithm intuitive to whoever I shared it with. It is a great illustration of how the most important part of explaining any procedure isn’t the list of steps you should take, but rather the intention-and-obstacle narrative that surrounds it. Such stories usually also make it plain how the algorithm could have emerged in the first place - in this case from an extremely simple sorting procedure. More broadly, far from merely allowing people to “understand something better” this type of information and understanding is the key that allows for further growth of knowledge.

The usual explanation

Here is how quick-sort is usually explained. Per Wikipedia:

“Quick-sort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort. The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.”

The partitioning itself is done via somewhat complicated array gymnastics. A complicated mathematical analysis then shows that while in the worst case this algorithm requires N^2 comparisons, it typically requires only around N log N. But why would you sort in this way? Why pick a pivot and divide the array? How does it avoid comparisons?

The intuitive explanation

Sorting is a problem of placing every element in a list into the right place in the list. It is about matching elements to places. This suggests two approaches for sorting:

• For every place find the right element to place into it

• For every element find the right place to place it in

Let’s say that we approach sorting a list in the second way - finding the right place for each element.¹ Given an element, what determines its right place? Let’s say that the list has 10 elements and for a given one 3 are smaller than it and 6 are larger. Then it is clear this element should be in the 4th place.

So here is a simple algorithm for sorting: given an element, compare it to every other element and count how many are smaller than it. If X elements are smaller, place it in (X+1)th place. If the list has N elements, this requires N^2 comparisons.

But here is a slight tweak to this algorithm we can make to avoid some unnecessary comparisons. If we pick an element and find that A elements are smaller than it and B are larger than it then there is no point in comparing the former with the latter. We already know what the answer would be. We can just sort the A elements separately and likewise for B. In this way we avoid A*B comparisons.

It may not be obvious but this algorithm is just… quick-sort.

Why is this more intuitive?

There is a difference between what one may call alive knowledge and dead knowledge. The former can be transformed and grow in the minds of whoever possesses it while the latter is essentially just information incapable of further growth. It can serve as a seed of new ideas.

To make a description of any procedure into a live piece of knowledge it doesn’t suffice to merely give a sequence of steps it consists of. This is the flaw of many cooking recipes. They tell you what to do but give no hint about why you do it. What change in the state of the ingredients are you trying to bring about by doing something? How does it relate to the kind of dish you ultimately want to have? Without this sort of understanding it is impossible to have any sense of how to change or improve a process. It is what can make cooking tedious rather than fascinating. All this surrounding information makes a piece of dead knowledge come alive.

In a similar vein, if an algorithm requires a complicated analysis to show that it works or that it works better than some other process it will always appear a bit mysterious. It will not be clear why anybody would have considered the procedure in the first place.

In the case of quick-sort one could reasonably ask - what is the point of picking the pivot? How does it relate with the goal of obtaining a sorted array with few comparisons? The conventional explanation tells you that the point is to divide the array into two pieces. But really the point is to sort the pivot into the right place. Once we have done so the splitting allows you to avoid making unnecessary comparisons based on the information you’ve collected along the way. This makes it plain how a sorted array actually emerges from the algorithm - one pivot selection at a time - and also leads into analysis of how many comparisons it avoids.

There is an old proverb: “Give a man a fish and you feed him for a day. Teach a man to fish and you feed him for a lifetime”. But if the man doesn’t just want to feed himself but his entire village then maybe that method won’t work. Merely teaching him how to fish might not be sufficient to make any progress on that - he could just forever be stuck with his inefficient fishing method. Just like with theoretical knowledge, moving forward always requires explanatory understanding. This type of information however usually gets little attention. More about its nature will be explored in future pieces.

1. Using the other strategy naturally leads to merge-sort/heap-sort-like algorithms.