# 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)$$.