Sorting Out Sorting

by Joey deVilla on September 24, 2007

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


Click here to see the video at a larger size.
Video length: 31 minutes, 15 seconds.

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:

C.A.R. Hoare: “I’M IN UR ARRAYS SORTING UR ELEMENTS”


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.

Cross-posted to the Tucows Developer Blog.

Previous post:

Next post: