Sorting Out Sorting

Here’s a gem from over a quarter-century ago: Sorting Out Sorting (running time 31:15), a film produced by the University of Toronto that uses then-impressive graphics to visually explain sorting algorithms:

The film is divided into three sections, each devoted to a category of sorting algorithm. These sections are:

1. Insertion sorts: Linear insertion, Binary insertion, Shellsort
2. Exchange sorts: Bubble sort, Shaker sort, Quicksort
3. Selection sorts: Straight selection, Tree selection, Heapsort

In case you’re not interested in sitting through 30-odd minutes of film and ice-cold ’70’s sci-fi synth music (which I found sort of mesmerizing), here’s the spoiler: Quicksort wins!*. I think this calls for a LOL-computer-scientist image of Quicksort’s creator, Tony Hoare:

Footnotes

* In most cases. If you want to sort data in an in-memory array or array-like structure that allows for constant speed random access, Quicksort is generally your best option, and it’s probably the algorithm used by your programming language’s built-in sort function.