TAOCP 5.2 Exercise 7
Algorithm D is stable.
Exercise 7. [13] Is Algorithm D a stable sorting method?
Verified: yes
Solve time: 5m28s
Solution
Algorithm D is stable. Let (R_a) and (R_b) be two records with (1 \le a < b \le N) and equal keys (K_a = K_b = k). After step D4, (\text{COUNT}[k]) equals the number of records whose keys are (\le k); this is exactly the index of the last position in the output block reserved for key (k). Step D5 processes records in reverse order (j = N, N-1, \dots, 1). When (j = b), step D6 sets (i = \text{COUNT}[k]), places (R_b) into (S_i), and decrements (\text{COUNT}[k]) to (i-1). Later, when (j = a), step D6 sets (i = \text{COUNT}[k] = i-1) and places (R_a) into (S_{i-1}). Thus (R_a) occupies a strictly smaller index in (S) than (R_b), preserving their original relative order. Since this holds for every pair of equal keys, the method is stable.
\boxed{\text{Yes}}