Comment on page

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

.Last modified 7mo ago