## Quick reference

Complexity
Worst case time
Best case time
Average case time
Space

#### 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:

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

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:

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

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:

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

## 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 time and 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.

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 time and space.

## What's next?

If you're ready to start applying these concepts to some problems, check out our mock coding interview questions.

They mimic a real interview by offering hints when you're stuck or you're missing an optimization.

. . .