Tutorial

Published on February 18, 2020

Joshua Hall

Because of the nature of comparison-based sorting, it’s mathematically impossible to improve much beyond `O(nlogn)`, like with merge sort and quick sort. Instead, we can be a bit more clever and avoid comparisons all together to get something closer to `O(n * m)`.

Prerequisites

A basic understanding of Big O Notation is essential to think about radix sort relative to other algorithms.

Concept

Radix sort, also known as bucket sort, is one of the oldest sorting algorithms and even pre-exists computers. It was used to sort punched cards back in the 1880s.

It’s based on the idea of having a sub-array, or bucket, for each type of data we need to compare, like A-Z or in our case 0-9. We take the first character/digit in each item, add the whole item to it’s corresponding bucket, then put them back into an array while retaining their new order.

We can then move on to the next character/digit and repeat the process. When an item runs out of characters/digits we’ll add it to the first bucket, since everything else is obviously larger/longer. When we’ve done this as many times as the number of digits/characters of the largest item, our array will have been completely sorted without making any pesky comparisons.

Graphic/Animation thanks to VisuAlgo.net

Practice Data

Since numbers are much simpler, we can practice with an array of them from 1 to 50.

``````const unsortedArr = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2];
``````

Utilities

Since we’re working with numbers, we want to start with the smallest number place and work up, so we’ll need a way to get each number at an index starting from the right.

The most intuitive way I’ve found is to take the number we want, convert it into a string, and select from it as an array with a negative index. If a number’s not at that index we can just return a zero so it’ll be placed in the front of our sorted array.

``````const getNum = (num, index) => {
const strNum = String(num);
let end = strNum.length - 1;
const foundNum = strNum[end - index];

if (foundNum === undefined) return 0;
else return foundNum;
};

console.log(getNum(4353, 2));
``````

Because we’re working back one digit at a time we need the algorithm to run as many times as the longest number, so if we have an item with 8 digits, it needs to be ran 8 times. Radix sort’s average complexity is `O(n * m)` because it’s the amount of items times the amount of times it needs to be ran.

To get how many times it should run we can search through the array for the largest number, then return its length.

``````const largestNum = arr => {
let largest = "0";

arr.forEach(num => {
const strNum = String(num);

if (strNum.length > largest.length) largest = strNum;
});

return largest.length;
};
``````

Implementation is pretty straight-forward, for every digit place we can use `Array.from` to create 10 empty buckets. For every item they’ll be placed in the corresponding bucket, when that’s done we’ll flatten the array of buckets into a single array to start over with the next character place. When we’ve reached the end of our longest digit our fully sorted array can be returned.

``````const radixSort = arr => {
let maxLength = largestNum(arr);

for (let i = 0; i < maxLength; i++) {
let buckets = Array.from({ length: 10 }, () => []);

for (let j = 0; j < arr.length; j++) {
let num = getNum(arr[j], i);

if (num !== undefined) buckets[num].push(arr[j]);
};
arr = buckets.flat();
};
return arr;
};

``````

Conclusion

While playing around with this, I tried it on an array of 5,000 items, to my utter amazement it was done in only 23 milliseconds! I don’t know about you, but I think that’s an incredible improvement over the other algorithms we’ve covered so far.

Thanks for learning with the DigitalOcean Community. Check out our offerings for compute, storage, networking, and managed databases.

Joshua Hall

author

While we believe that this content benefits our community, we have not yet thoroughly reviewed it. If you have any suggestions for improvements, please let us know by clicking the “report an issue“ button at the bottom of the tutorial.

Ask a questionSearch for more help

﻿

You can type !ref in this text area to quickly search our full set of tutorials, documentation & marketplace offerings and insert the link!

Click below to sign up and get \$200 of credit to try our products over 60 days!

Featured on Community

Hollie's Hub for Good

Working on improving health and education, reducing inequality, and spurring economic growth? We'd like to help.

Become a contributor

Get paid to write technical tutorials and select a tech-focused charity to receive a matching donation.

Welcome to the developer cloud

DigitalOcean makes it simple to launch in the cloud and scale up as you grow — whether you're running one virtual machine or ten thousand.