A visualization of the Radix sort algorithm. We start with a simpler algorithm: Pigeonhole sort (sometimes also called Bucket sort or Bin sort, see below). Then discuss stability of sorting algorithm, and finally Radix sort.
About Radix Sort
Radix sort dates back to Hollerith’s sorting machines from around 1890.
The machines only did Pigeonhole sort, and the human operators were instructed how to use this as a step in Radix Sort. Initial instructions were for MSD Radix Sort, but apparently an anonymous human operator discovered LSD Radix Sort is easier.
About Pigeonhole sort
Usually Pigeonhole sort is defined with an additional initial pass, of finding the range of possible values in the list, instead of these being provided in advance, as in the video.
There’s some confusion over the names of a group of closely related algorithms.
Pigeonhole sort is called Bucket sort or Bin sort. But usually Bin/Bucket sort is defined in a different way, as an algorithm where each ‘bucket’ or stack contains a range of possible values, and not just one. Each bucket is then sorted using some algorithm. For example, if the elements are real numbers in the range [0…1], we can divide them to ten buckets [0…0.1], [0.1…0.2], [0.2…0.3], … [0.9…1]. Then sort each bucket using, for example, quick sort. Since supposedly only a few elements will fall in each bucket, sorting it should be fast.
In bucket sort, we can also sort each bucket using Bucket sort recursively. For example, the bucket 0…0.1 for the example above will be further split to [0…0.01], [0.01…0.02] … [0.09..0.1]. This is the same as MSD Radix sort.
Another similar algorithm is Counting sort. It is similar to Pigeonhole sort, except that it just counts the number of values in each bucket, instead of actually moving the element into to the bucket.
References
Cormen, Thomas H. Algorithms unlocked. Mit Press, 2013.
Defines “Bucket sort” in the more general sense, and provides some background history on Radix sort.
Knuth, Donald E. Art of Computer Programming, Volume 3, Sorting and Searching.
Chapter 5 discusses the history of Radix sort in more detail.