Getting To The Root Of Sorting With Radix Sort

Vaidehi Joshi
Jul 24, 2017 · 14 min read
Image for post
Image for post
Getting to the root of radix sort!

A rooting interest in the radix

Image for post
Image for post
A radix is another term for ‘base’.
Image for post
Image for post
The word radix comes from the Latin word for “root”.
Image for post
Image for post
Radix sort: a definition
Image for post
Image for post
How can we alphabetize this list of houseplants?
Image for post
Image for post
Grouping words by the different letters
Image for post
Image for post
Our plant names are back in order!
Image for post
Image for post
Radix sort handles sorting one digit at a time.

Putting down (radix) roots

Image for post
Image for post
Two variations on radix sort
Image for post
Image for post
Rewriting our array elements to have the same number of digits

The least significant digit is the smallest digit in each number; if we’re dealing with base ten integers, the least significant digit will be number in the units place.

Image for post
Image for post
LSD radix sort: step 1 [EDIT: there is a typo here! The first digit on the right (the rightmost digit) is always the UNITS, not the tens. Oops! It goes units, tens, hundreds, and so on..]
Image for post
Image for post
LSD radix sort: step 2 [EDIT: there is a typo here! The second digit on the right is always the TENS, not the hundreds. Oops! It goes units, tens, hundreds, and so on..]
Image for post
Image for post
LSD radix sort: step 3 [EDIT: there is a typo here! The third digit on the right is always the HUNDREDS, not the thousands. Oops! It goes units, tens, hundreds, thousands, and so on..]
Image for post
Image for post
LSD radix sort data transformations
Image for post
Image for post
Radix sort’s time complexity at runtime

A deep-rooted sorting history

Image for post
Image for post
How does radix sort stack up?
Image for post
Image for post
Hollerith machines, The Art of Computer Programming

Resources

basecs

Exploring the basics of computer science, every Monday, for…

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store