 ## 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: 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 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 stores the number of items with a 0 in this bit # counts 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 stores the index where we should put the next item # with a 0 in this bit. # indices 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] # 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.

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

. . .