> 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.4-summary.md).

# 35.4 Summary

**Terminology.**

* Radix - just another word for ‘base’ as in the base of a number system. For example, the radix for words written in lowercase English letters is 26. For number written in Arabic numerals it is 10.
* Radix sort - a sort that works with one character at a time (by grouping objects that have the same digit in the same position).
* Note: I will use ‘character’ and ‘digit’ interchangably in this study guide.

**Counting Sort.** Allows you to sort $$N$$ keys that are integers between $$0$$ and $$R-1$$ in $$\Theta(N+R)$$time. Beats linearithmic lower bound by avoiding any binary compares. This is a completely different philosophy for how things should be sorted. This is the most important concept for this lecture.

**LSD.** In the LSD algorithm, we sort by each digit, working from right to left. Requires examination of $$\Theta(WN)$$digits, where $$W$$is the length of the longest key. Runtime is $$\Theta(WN+WR)$$, though we usually think of $$R$$ as a constant and just say $$\Theta(WN)$$. The $$\Theta(WR)$$ part of the runtime is due to the creation fo length $$R$$ arrows for counting sort. We usually do LSD sort using counting sort as a subroutine, but it’s worth thinking about whether other sorts might work as well.

**LSD vs Comparison Sorting.** Our comparison sorts, despite requiring $$\Theta(N\*logN)$$ time, can still be faster than LSD sort. For extremely large N, LSD sort will naturally win, but log N is typically pretty small. Know which algorithm is best in the two extreme cases of very long dissimilar strings and very long, nearly equal strings.

**MSD.** In MSD sorting, we work from left to right, and solve each resulting subproblem independently. Thus, for each problem, we may have as many as $$R$$ subproblem. Worst case runtime is exactly the same as LSD sort, $$\Theta(WN+WR)$$, though can be much better. In the very best case, where we only have to look at the top character (only possible for $$R>N$$), we have a runtime of $$\Theta(N+R)$$.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

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