> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/35.-radix-sorts/35.1-counting-sort.md). # 35.1 Counting Sort Imagine if instead of driving a slow Honda Civic, we started driving a fast Ferrari. Unfortunately, we won't actually be driving in a Ferrari today, but we will witness a blazing fast algorithm that's just as fast called Radix Sorts. When sorting an array, sorting requires $$\Omega(N \log N)$$compare operations in the worst case (array is sorted in descending order). Thus, the ultimate comparison based sorting algorithm has a worst case runtime of $$\Theta(N \log N)$$. From an asymptotic perspective, that means no matter how clever we are, we can never beat Merge Sort’s worst case runtime of $$\Theta(N \log N)$$. But what if we don't compare at all?

Left is original, right is ordered output

Essentially what just happened is that we first made a new array of the same size and then just copied all of the # indexes to the correct location. So first we look at 5 Sandra Vanilla Grimes and then copy this over to the 5th index in our new array. This does guarantee $$\Theta(N)$$ worst case time. However what if we were working with * Non-unique keys. * Non-consecutive keys. * Non-numerical keys. All of these cases are complex cases that aren't so simple to deal with. Essentially what we can do is create a simpler method which is to: * Count number of occurrences of each item. * Iterate through list, using count array to decide where to put everything. Bottom line, we can use counting sort to sort $$N$$ objects in $$\Theta(N)$$ time.