Paper: “Engineering a Sort Function”

“Engineering a Sort Function” by John L. Bentley and M. Douglas McIlroy gives a nice insight how theoretical algorithm design is applied in software engineering. I think I came across the paper, because Go’s sort function implementation is based on the described algorithm.

The paper outlines how the unstable sort algorithm has evolved over several iterations during development. It is based on Quicksort, but uses insertion sort for arrays of size ≤7. The solution to Dijkstra’s Dutch national flag problem gives the partition method for QuickSort. Pivot elements are selected with the median of 3 (array size >40) or median of 9 (array size ≤40). You can also see how cost models are applied such that asymptotic behavior becomes less important compared to the expense of particular operations. I think it is interesting, because cost models are not taught here at University of Technology, Graz, whereas asymptotic behavior is focused. However, this model fails where the comparison function can be arbitrary according to the interface and so the actual expense of comparison cannot be estimated.

In the end, I think it is a nice read for 2 hours assuming you are familiar with basic algorithm design.

“[…] This algorithm is easy to describe, and also easy to get wrong—Knuth tells horror stories about inefficient partitioning algorithms.”

“The key to performance is elegance, not battalions of special cases.”

Paper: “Engineering a Sort Function”