3 ms·
> In every decent programmer’s toolbox lies a strange weapon called a Radix Sort. Where does it come from ? Who invented it ? I don’t know. Bit of a tangent, b
by colmvp 5y ago
> In every decent programmer’s toolbox lies a strange weapon called a Radix Sort. Where does it come from ? Who invented it ? I don’t know.
Bit of a tangent, but at first this kind of caught me off guard because in this day and age it's easy to search for deeper info on established concepts and most articles would briefly have this answer (if the author cared to mention the history at all) but then I had to remind myself the post was created in 2000, before Wikipedia (Radix Sort was added to Wikipedia in 2001), explanatory YouTube videos, and tons of writeups made us into instant "experts" of every field.
- OskarS 5y agoAn invaluable source for information like this (that did indeed exist in 2001) is The Art of Computer Programming by Donald Knuth. Knuth is extremely diligent in documenting the history of all algorithms he describes (arguably, TAoCP is the best source-book for the history of all computer science) and he has the following to say on the topic of Radix sort: > The sorting method just described is not immediately obvious, and it isn't clear who first discovered the fact that it works so conveniently. A 19-page pamphlet entitled "The Inventory Simplified," published by the Tabulating Machines Company division of IBM in 1923, presented an interesting Digit Plan method for forming sums of products in their Electric Sorting Machine ... This punched-card tabulating method leads naturally to the discovery of least-significant-digit-first radix sorting, so it probably became known to the machine operators. The first published reference to this principle for sorting appears in L. J. Comrie's early discussion of punched-card equipent [Transactions of the Office Machinery Users' Assoc., Ltd (1929)] > ...most people rejected the idea of radix sorting within a computer, until H.H. Seward['s master thesis in 1954] pointed out that... [<technical details omitted>] Presumably, this is a method that has been discovered and rediscovered many times by many programmers and punch-card operators, but that H. H. Seward made it practical for digital computers in 1954. PS. TAoCP is awesome. Even if you can't follow the more advanced math, just having this book on the shelf to look up stuff like this is lovely if you do this kind of thing professionally. Knuth is just a fantastic scholar and teacher. Just flipping through the things is a joy.
- chasd00 5y agoi just looked TAoCP up on amz, the box set is $600. that's... pricey. sheesh
- actually_a_dog 5y agoI'm seeing used sets online for under $250. That seems well worth it to me, even if you only reference it once every couple years.