Week 8: Radix Sort

Chris Tralie

Overview / Logistics

We saw in class (click here for a video) that the lower bound for any possible sort that's based on comparisons is Ω(N log(N)). So if we have any hope of beating this, we have to think of a completely different strategy. We'll start with a simple example first known as "counting sort"


Counting Sort

What we can do is have a bunch of "bins" or "buckets," ordered in sequence in an array, where there's a bin for each possible value in our list. We can then loop through the bins from left to right and extract the elements in order. The code below shows this

Question

What is the time and space complexity of the above algorithm?


Radix Sort

Depending on the maximum element, counting sort can be pretty inefficient. But there's a way to use it as a subroutine in a more efficient sort. If we're careful on how we implement counting sort, it can be done so that it's stable. What we can do, then, is apply counting sort one digit at a time, from the right most digit left. This is known as Least Significant Digit Radix Sort. The table below shows this.

Original Order684559629192835763707359972327775480459970472600396314705
1s Place706001924727637236847548043148357053967072775596293599599
10s Place600804705707931472362983575455935976370472277684192396599
100s Place970192277314359396472559599600629684705707723754763804835

Code from Class