[Algo] 8.3 Radix sort

Radix sort 的原理

假設 input array 裡的每個 element 都是 d-digit，整個 radix sort 的精神就是從 least significant bit 開始往 most significant bit 排序，在這邊我們用來排序每個 bit 的是用有 stable 性質的 sorting algorithm (counting sort)，經過 d 個 pass 之後，整個演算法就大功告成了，注意不是從 most significant bit 開始喔！

Radix sort algorithm

@{
\proc{Radix-Sort}(A, d)
\li \For i = 1 \;\textbf{to}\; d
\li \;\;\;\;\textup{use a stable sort to sort array}\; A \;\textup{on digit}\; i
}@

Lemma 8.3
Given $n$ $d$-digit numbers in which each digit can take on up to $k$ possible values, RADIX-SORT correctly sorts these numbers in $\Theta(d(n + k))$ time.
proof: 當每個 digit 的值域 k 不要太大，COUNTING-SORT是個不錯的選擇。每個 pass 裡，我們都花 $\Theta(n + k)$ 的時間來排序 $n$ 個 digit。總共有 $d$ 個 passes，所以總共需要 $\Theta(d(n + k))$ 的 running time。$\blacksquare$

當 $d$ 是常數，而 $k = O(n)$，RADIX-SORT 就是 linear time 的 sorting algorithm。

Lemma 8.4
Given $n$ $b$-bit numbers and any positive integer $r \leq b$, RADIX-SORT correctly sorts these numbers in $\Theta((b/r)(n + 2^r))$ time.
proof: 在 RADIX-SORT 裡面，我們每次排序都只針對一個 digit 去做 stable sort，也就是它的值域只有 0 跟 1 而已，其實也可以把 $r$ 個 digit 看成一個 pass 來做 stable sort，變成每個 pass 所作 sorting 的值域變成 $2^r - 1$，這樣我們只要 $\lceil b/r \rceil$ 次 pass 就可以完成了。
於是整個 running time 就是 $\Theta(d(n + k)) = \Theta(\lceil b/r \rceil(n + 2^r - 1)) = \Theta((b/r)(n + 2^r)) \blacksquare$

如何選擇適當的 r
(1) $b < \lfloor \lg n \rfloor$：此時 $n + 2^r = \Theta(n)$，於是令 $r = b$ 時，running time 是 $(b/b)(n + 2^b) = \Theta(n)$，這樣就會是 asymptotically optimal 的了。
(2) $b \geq \lfloor \lg n \rfloor$：此時選擇 $r= \lfloor \lg n \rfloor$，整個 running time 就是 $\Theta((b/\lg n)(n + n)) = \Theta(bn/ \lg n)$