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

 

<figure><img src="https://2316889115-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FCLYj7ccqvV6l4Pt9R0w5%2Fuploads%2FfO3Soswe0bCDHeCuMipB%2FScreen%20Shot%202023-04-15%20at%202.26.42%20AM.png?alt=media&#x26;token=d0524a55-9ab4-45fa-a7d0-e267facc29bd" alt=""><figcaption><p>Left is original, right is ordered output</p></figcaption></figure>

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&#x20;

* 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.&#x20;


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs61b-2.gitbook.io/cs61b-textbook/35.-radix-sorts/35.1-counting-sort.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.