Radix Sort Algorithm: Time Complexity & Code

Q: How does radix sort work?

It groups numbers by each digit in turn—starting from the least significant digit—using a stable sort at each step, so after the last digit the whole list is sorted.

Q: What is the time complexity of radix sort?

O(d·(n + b)), where n is the number of items, d is the number of digits in each one, and b is the base (how many values each digit can take). For fixed-width integers, d and b are constants, so radix sort runs in O(n) time. It uses O(n + b) extra space.

Q: Is radix sort stable?

Yes. The usual least-significant-digit-first version has to use a stable sort for each digit; that's what preserves the order from the digits it already sorted when later digits tie.

Q: What's the difference between radix sort and counting sort?

Counting sort takes O(n + k) time, where k is the range of values, so it's only practical when that range is small. Radix sort runs counting sort once per digit, so each pass only needs one counter per possible digit value, which makes it practical for numbers with a huge range.

Q: When should you use radix sort?

For sorting integers or fixed-length keys, especially large datasets where the key length is small relative to the number of items.

Quick reference

	Complexity
Worst case time	O(n)
Best case time	O(n)
Average case time	O(n)
Space	O(n)

Radix sort is a non-comparison sorting algorithm that sorts integers one digit at a time, from the least significant digit to the most significant, using a stable sort (usually counting sort) on each digit. In general it takes O(ℓ·(n + k)) time for n numbers with \ell digits that can each take on k values. For fixed-width integers (like 64-bit ints), \ell and k are constants, which is where the O(n) in the table above comes from.

Strengths:

Linear Time. Radix sort takes time to sort n integers with a fixed number of bits.
Punch card Friendly. Way back in the day (like the 50's and 60's), programs were written on these cards with holes in them, called punch cards. Radix sort works really well for sorting these physical cards. (It was a big deal at the time.)

Weaknesses:

Restricted inputs. Radix sort only works when sorting numbers with a fixed number of digits. It won't work for arbitrarily-large numbers.

How It Works

Radix sort works by sorting the input numbers one digit at a time.

As an example, let's sort this array:

Unsorted Input: [127, 324, 173, 4, 38, 217, 134].

First, we'll sort on the one's place:

First, we'll focus on the ones place: [12{7}, 32{4}, 17{3}, {4}, 3{8}, 21{7}, 13{4}].

Any stable sorting algorithm can be used here. In practice, counting sort works well, since the digits can only take on a small number of values (i.e.: 0 - 9 for base-10 numbers; 0 - 1 for base-2 numbers).

Here's what sorting on the one's place gets us:

Sorting [12{7}, 32{4}, 17{3}, {4}, 3{8}, 21{7}, 13{4}] by the ones place, we have [173, 324, 4, 134, 127, 217, 38].

Then, we'll sort on the ten's place:

Sorting by the 10's place, [1{7}3, 3{2}4, {0}4, 1{3}4, 1{2}7, 2{1}7, {3}8] becomes [04, 217, 324, 127, 134, 38, 173].

Notice how whenever there was a tie in the tens place the number with a lower ones digit came first. This is why using a stable sorting algorithm is important. It means that if there's a tie on the current digit we'll fall back to how the numbers were ordered based on the digits we already sorted.

And finally, we'll sort on the hundred's place:

Sorting by the 100's place, [{0}04, {2}17, {3}24, {1}27, {1}34, {0}38, {1}73] becomes [004, 038, 127, 134, 173, 217, 324].

Once we've sorted all the digits, we're done! :)

Final sorted output: [4, 38, 127, 134, 173, 217, 324].

Implementation

Here's how we'd code it up. We'll assume that all the inputs are 64-bit integers.

Since the numbers are stored in binary, we'll run our radix sort on their binary digits (instead of the digits in their base-10 representations).

We'll be using bit shifting and bitwise ands to extract individual bits from items in the input array.

/* * Returns the value of the bit at index 'bit' in 'number' */ private static int bitValue(int number, int bit) { int mask = 1 << bit; if ((number & mask) != 0) { return 1; } return 0; } /* * Arrange the items in theArray based on the value of * a specific bit. This doesn't fully sort the array (it * just sorts by a specific bit), but we'll use it for radix * sort. */ private static int[] countingSort(int[] theArray, int bit) { // counts[0] stores the number of items with a 0 in this bit // counts[1] stores the number of items with a 1 in this bit int[] counts = new int[]{0, 0}; for (int item : theArray) { counts[ bitValue(item, bit) ] += 1; } // indices[0] stores the index where we should put the next item // with a 0 in this bit. // indices[1] stores the index where we should put the next item // with a 1 in this bit. // // the items with a 0 in this bit come at the beginning (index 0). // the items with a 1 in this bit come after all the items with a 0. int[] indices = new int[]{0, counts[0]}; // output array to be filled in int[] sortedArray = new int[theArray.length]; for (int item : theArray) { int itemBitValue = bitValue(item, bit); // place the item at the next open index for its bit value sortedArray[ indices[itemBitValue] ] = item; // the next item with the same bit value goes after this item indices[itemBitValue] += 1; } return sortedArray; } /* * Use counting sort to arrange the numbers, from least significant * bit to most significant bit. */ public static int[] radixSort(int[] theArray) { for (int bitIndex = 0; bitIndex < 64; bitIndex++) { theArray = countingSort(theArray, bitIndex); } return theArray; }

Complexity

Radix sort takes O(ℓ·(n + k)) time and O(n + k) space, where n is the number of items to sort, \ell is the number of digits in each item, and k is the number of values each digit can have.

You'll also see this written as O(d·(n + b)), for d digits in base b. Same idea, different letters.

This time complexity comes from the fact that we're calling counting sort one time for each of the \ell digits in the input numbers, and counting sort has a time complexity of .

The space complexity also comes from counting sort, which requires space to hold the counts, indices, and output arrays.

In many implementations, including ours, we assume that the input consists of 64-bit integers. This means that the number of digits, \ell is a constant (64). With a binary number, each digit can either be a zero or a one, meaning that k is also a constant (2). With these assumptions, radix sort becomes O(n) time and O(n) space.

Radix Sort vs. Counting Sort

Radix sort is built on top of counting sort, so it's worth knowing when to reach for each one:

	Radix sort	Counting sort	Comparison sorts (merge sort, quicksort, ...)
Time	O(ℓ·(n + k)), where k is the number of values per digit	O(n + k), where k is the range of the input values	O(n log n) at best
Space	O(n + k)	O(n + k)	Depends on the algorithm
Stable?	Yes (as long as each pass is stable)	Yes (the standard version)	Some are (merge sort), some aren't (quicksort)
Best for	Lots of integers (or fixed-length keys) with a wide range of values	Integers that fall in a small range	Anything you can compare

Counting sort is great when the range of values is small, but sorting numbers that go up to a billion would need a billion counters. Radix sort gets around that by running counting sort once per digit, so each pass only needs as many counters as there are possible digit values.

Sorting interview questions to practice

Each one walks you through a real coding interview problem one hint at a time.

Your first 3 questions are free. Just sign in, no credit card.

Interview coming up?

Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.

No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.

No spam. One-click unsubscribe whenever.

You're in! Head over to your email inbox right now to read day one!

Frequently Asked Questions

How does radix sort work?