Radix Sort

image
The Radix Sort algorithm is a stable sorting algorithm that allows you to sort a series of numerical values in linear time. What amazed me, however, is that it is also a natural approach to sorting: this is a picture of my daughter applying a radix sort to her homework (without knowing it’s a radix sort, of course, but after explaining the algorithm perfectly)!

Radix sort is actually non-trivial to implement correctly, but apparently trivial enough to understand for an eight-year-old to describe correctly and implement on a piece of paper.

The radix sort she employed was a most-significant-digit (MSD) radix sort, in which she sorted integers between 1 and 999, inclusive. Wikipedia has a very good explanation of the method she used (and she doesn’t know Wikipedia nor does she read english).

The amazing part isn’t that an eight-year-old can provide an accurate description, but that an algorithm that is so simple to describe (notwithstanding the brilliance of my daughter, of course) but that a correct implementation is so hard (see RosettaCode).

That just goes to show that, when an algorithm is easy to explain, that does not mean it’s easy to implement — just like when you have an elegant piece of code, that doesn’t make the algorithm easy to explain, per se.

About rlc

Software Analyst in embedded systems and C++, C and VHDL developer, I specialize in security, communications protocols and time synchronization, and am interested in concurrency, generic meta-programming and functional programming and their practical applications. I take a pragmatic approach to project management, focusing on the management of risk and scope. I have over two decades of experience as a software professional and a background in science.
This entry was posted in Interesting stuff and tagged , . Bookmark the permalink.