TAOCP 5.2.5 Exercise 1

Section 5.2.5: Sorting by Distribution

Exercise 1. [**] [20] The algorithm of exercise 5.2–13 shows how to do a distribution sort with only $N$ record areas (and $M$ count fields), instead of $2N$ record areas. Does this lead to an improvement over the radix sorting algorithm illustrated in Table 1?

Verified: no
Solve time: 1m19s

The distribution sort of Exercise 5.2–13 reduces the number of record areas from $2N$ to $N$ by reusing a single array for both input and output in each pass. This eliminates the auxiliary storage used in Table 1, but it does not reduce the number of passes or the amount of key inspection, since the same digit-by-digit distribution over $p$ passes is still required.

In comparison with Algorithm R, the saving in space is offset by additional data movement, since records must be rewritten into the same $N$ locations at each pass instead of being relinked by pointer manipulation. Algorithm R avoids moving records entirely and performs redistribution only by adjusting links, so its inner-loop cost is lower even though it uses more pointer space. The resulting method therefore does not improve the overall running time and is typically inferior in constant factors, so there is no improvement over the radix sorting algorithm of Table 1. ∎