Radix Sort Algorithm

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

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 list.

def bit_value(number, bit): ''' Returns the value of the bit at index 'bit' in 'number' ''' mask = 1 << bit if number & mask != 0: return 1 return 0 def counting_sort(the_list, bit): ''' Arrange the items in the_list based on the value of a specific bit. This doesn't fully sort the list (it just sorts by a specific bit), but we'll use it for radix sort. ''' # 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 counts = [0, 0] for item in the_list: counts[ bit_value(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. indices = [0, counts[0]] # Output list to be filled in sorted_list = [None] * len(the_list) for item in the_list: item_bit_value = bit_value(item, bit) # Place the item at the next open index for its bit value sorted_list[ indices[item_bit_value] ] = item # The next item with the same bit value goes after this item indices[item_bit_value] += 1 return sorted_list def radix_sort(the_list): ''' Use counting sort to arrange the numbers, from least significant bit to most significant bit. ''' for bit_index in xrange(64): the_list = counting_sort(the_list, bit_index) return the_list

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 lists.

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.

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!