Chapter 8 Sorting in Linear Time 839 Figure 8.3 The operation of radix sort on a list of seven 3-digit numbers. The leftmost column is the input. The remaining columns show the list after successive sorts on increasingly significant digit positions. Shading indicates the digit position sorted on to produce each list from the previous one. In a typical computer, which is a sequential random-access machine, we some times use radix sort to sort records of information that are keyed by multiple fields. For example, we might wish to sort dates by three keys: year, month, and day. We could run a sorting algorithm with a comparison function that, given two dates, compares years, and if there is a tie, compares months, and if another tie occurs. compares days. Alternatively, we could sort the information three times with a stable sort: first on day, next on month, and finally on year. The code for radix sort is straightforward. The following procedure assumes that each element in the n-element array A has d digits, where digit 1 is the lowest-order digit and digit d is the highest-order digit. RADIX-SORT(A, d) 1 for i = 1 to d 2 use a stable sort to sort array A on digiti 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 eld(n + k)) time if the stable sort it uses takes (n + k) time. Proof The correctness of radix sort follows by induction on the column being 2. Use Figure 8.3 on page 198 as a model, illustrate the operation of RADIX-SORT on the following list of words: ROW, JAW, WAX, FIZ, BIZ, FEZ, WIZ, ZIN, MIX, PAX, NOW, BOX, JAM, JAB, ZIP, JUG, MOB, DIG