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 Order	684	559	629	192	835	763	707	359	9	723	277	754	804	599	70	472	600	396	314	705
1s Place	70	600	192	472	763	723	684	754	804	314	835	705	396	707	277	559	629	359	9	599
10s Place	600	804	705	707	9	314	723	629	835	754	559	359	763	70	472	277	684	192	396	599
100s Place	9	70	192	277	314	359	396	472	559	599	600	629	684	705	707	723	754	763	804	835

---

Code from Class