TAOCP 5.2.4 Exercise 23

Section 5.2.4: Sorting by Merging

Exercise 23. [M30] Exercises 13 and 14 analyze a "bottom-up" or iterative version of merge sort, where the cost $c(N)$ of sorting $N$ items satisfies the recurrence

$$c(N) = c(2^k) + c(N - 2^k) + f(2^k, N - 2^k) \quad \text{for } 2^k < N \le 2^{k+1}$$

and $f(m, n)$ is the cost of merging $m$ things with $n$. Study the "top-down" or divide-and-conquer recurrence

$$c(N) = c(\lceil N/2 \rceil) + c(\lfloor N/2 \rfloor) + f(\lceil N/2 \rceil, \lfloor N/2 \rfloor) \quad \text{for } N > 1,$$

which arises when merge sort is programmed recursively.

5.2.5. Sorting by Distribution

We come now to an interesting class of sorting methods that are essentially the exact opposite of merging, when considered from a standpoint we shall discuss

in Section 5.4.7. These methods were used to sort punched cards for many years, long before electronic computers existed. The same approach can be adapted to computer programming, and it is generally known as “bucket sorting,” “radix sorting,” or “digital sorting,” because it is based on the digits of the keys.

Suppose we want to sort a 52-card deck of playing cards. We may define

A < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K,

as an ordering of the face values, and for the suits we may define

♣ < ♦ < ♥ < ♠

One card is to precede another if either (i) its suit is less than the other suit, or (ii) its suit equals the other suit but its face value is less. (This is a particular case of lexicographic ordering between ordered pairs of objects; see exercise 5-2.) Thus

A♣ < 2♣ < ··· < K♣ < A♦ < ··· < Q♠ < K♠.

We could sort the cards by any of the methods already discussed. Card players often use a technique somewhat analogous to the idea behind radix exchange: First they divide the cards into four piles, according to suit, then they fiddle with each individual pile until everything is in order.

But there is a faster way to do the trick! First deal the cards face up into 13 piles, one for each face value. Then collect these piles by putting the aces on the bottom, the 2s face up on top of them, then the 3s, etc., finally putting the kings (face up) on top. Turn the deck face down and deal again, this time into four piles for the four suits. (Again you turn the cards face up as you deal them.) By putting the resulting piles together, with clubs on the bottom, then diamonds, hearts, and spades, you’ll get the deck in perfect order.

The same idea applies to the sorting of numbers and alphabetic data. Why does it work? Because (in our playing card example) if two cards go into different piles in the final deal, they have different suits, so the one with the lower suit is lowest. But if two cards have the same suit (and consequently go into the same pile), they are already in proper order because of the previous sorting. In other words, the face values will be in increasing order, on each of the four piles, as we deal the cards on the second pass. The same proof can be abstracted to show that any lexicographic ordering can be sorted in this way; for details, see the answer to exercise 5-2, at the beginning of this chapter.

The sorting method just described is not immediately obvious, and it isn’t clear who first discovered the fact that it works so conveniently. A 19-page pamphlet entitled “The Inventory Simplified,” published by the Tabulating Machines Company division of IBM in 1923, presented an interesting Digit Plan method for forming sums of products on their Electric Sorting Machine: Suppose, for example, that we want to multiply the number punched in columns 1–10 by the number punched in columns 23–25, and to sum all of these products for a large number of cards. We can sort first on column 25, then use the Tabulating Machine to find the quantities $a_0, a_1, \ldots, a_9$, where $a_x$ is the total

of columns 1–10 summed over all cards having & in column 25. Then we can

sort on column 24, finding the analogous totals $b_1, b_2, \dots, b_9$; also on column 23,

obtaining $c_1, c_2, \dots, c_9$. The desired sum of products is easily seen to be

This punched-card tabulating method leads naturally to the discovery of least-

significant-digit-first radix sorting, so it probably became known to the machine

operators. The first published reference to this principle for sorting appears in

L. J. Comrie’s early discussion of punched-card equipment [_Transactions of the

Office Machinery Users’ Assoc., Ltd._ (1929), 25–37, especially page 28].

In order to handle radix sorting inside a computer, we must decide what to

do with the piles. Suppose that there are $M$ piles; we could set aside $M$ areas of

memory, moving each record from an input area into its appropriate pile area.

But this is unsatisfactory, since each area must be large enough to hold $N$ items,

and $(M + 1)N$ record spaces would be required. Therefore most people rejected

the idea of radix sorting within a computer, until H. H. Seward [Master’s thesis,

M.I.T. Digital Computer Laboratory Report R-232 (1954), 25–28] pointed out

that we can achieve the same effect with only $2N$ record areas and $M$ count fields.

We simply count how many elements will lie in each of the $M$ piles, by making

a preliminary pass over the data; this tells us precisely how to allocate memory

for the piles. We have already made use of the same idea in the “distribution

counting sort,” Algorithm 5.2D.

Thus radix sorting can be carried out as follows: Start with a distribution

sort based on the least significant digit of the keys (in radix $M$ notation), moving

records from the input area to an auxiliary area. Then do another distribution

sort, on the next least significant digit, moving the records back into the original

input area; and so on, until the final pass (on the most significant digit) puts all

records into the desired order.

If we have a decimal computer with 12-digit keys, and if $N$ is rather large, we

can choose $M = 1000$ (considering three decimal digits as one radix-1000 digit);

then sorting will be complete in four passes, regardless of the size of $N$. Similarly,

if we have a binary computer and a 40-bit key, we can set $M = 1024 = 2^{10}$ and

complete the sorting in four passes. Actually each pass consists of three parts

(counting, allocating, moving); E. H. Friend [JACM 3 (1956), 151] suggested

combining two of those parts at the expense of $M$ more memory locations, by

accumulating the counts for pass $k + 1$ while moving the records on pass $k$.

Table 1 shows how such a radix sort can be applied to our 16 example

numbers, with $M = 10$. Radix sorting is generally not useful for such small $N$,

so a small example like this is intended to illustrate the sufficiency rather than

the efficiency of the method.

An alert, “modern” reader will note, however, that the whole idea of mak-

ing digit counts for the storage allocation is tied to old-fashioned ideas about

sequential data representation. We know that linked allocation is specifically

designed to handle a set of tables of variable size, so it is natural to choose a

linked data structure for radix sorting. Since we traverse each pile serially, all

Verified: no
Solve time: 2m45s

---

Setup

The top-down (divide-and-conquer) merge sort splits a file of (N) records into two subfiles of sizes (\lceil N/2\rceil) and (\lfloor N/2\rfloor), sorts them recursively, and merges the results. If (c(N)) denotes the total cost of sorting (N) items and (f(m,n)) is the cost of merging two sorted lists of lengths (m) and (n), then for (N>1)

[ c(N)=c(\lceil N/2\rceil)+c(\lfloor N/2\rfloor)+f(\lceil N/2\rceil,\lfloor N/2\rfloor),\qquad c(1)=0. ]

In the context of Algorithm M the two most natural cost measures are

• comparisons: (f(m,n)=m+n-1) (worst case),
• data moves: (f(m,n)=m+n).

We analyse the recurrence for both choices.

Solution

Case 1: (f(m,n)=m+n-1) (comparisons)

The recurrence becomes

[ c(N)=c(\lceil N/2\rceil)+c(\lfloor N/2\rfloor)+N-1,\qquad c(1)=0. ]

Let (k=\lceil\log_2 N\rceil); thus (2^{k-1}<N\le 2^k).
We claim that for all (N\ge 1)

[ \boxed{c(N)=Nk-2^k+1}. ]

Proof by induction on (N).
Base (N=1): (k=0) and the formula gives (1\cdot0-1+1=0).
Inductive step: Assume the formula holds for all values (<N). For (N>1) set (N_1=\lceil N/2\rceil), (N_2=\lfloor N/2\rfloor). Then (N_1+N_2=N). Because (2^{k-1}<N\le 2^k) we have (2^{k-2}<N/2\le 2^{k-1}), hence (\lceil\log_2 N_1\rceil=\lceil\log_2 N_2\rceil=k-1). By the induction hypothesis

[ c(N_1)=N_1(k-1)-2^{k-1}+1,\qquad c(N_2)=N_2(k-1)-2^{k-1}+1. ]

Adding and using (N_1+N_2=N) yields

[ c(N_1)+c(N_2)=N(k-1)-2^k+2. ]

The recurrence adds (N-1), therefore

[ c(N)=N(k-1)-2^k+2+N-1=Nk-2^k+1. ]

This completes the induction. ∎

Case 2: (f(m,n)=m+n) (data moves)

The recurrence is

[ c(N)=c(\lceil N/2\rceil)+c(\lfloor N/2\rfloor)+N,\qquad c(1)=0. ]

Every merge in the recursion tree corresponds to an internal node; a binary tree with (N) leaves has exactly (N-1) internal nodes. Compared with Case 1 each merge costs exactly one extra unit, so the total cost increases by (N-1). Hence

[ \boxed{c(N)=\bigl(Nk-2^k+1\bigr)+(N-1)=Nk-2^k+N}. ]

One may also verify this formula directly by induction (the inductive step simply replaces the added (N-1) by (N)).

Asymptotics

Since (k=\lceil\log_2 N\rceil=\log_2 N+O(1)), both cost functions satisfy

[ c(N)=N\log_2 N+O(N). ]

For (N=2^k) (a power of two) the formulas simplify to

• comparisons: (c(N)=N\log_2 N-N+1),
• moves: (c(N)=N\log_2 N).

Verification

We check small values against the recurrence directly.

(N)	(k)	(c_{\text{comp}}(N))	(c_{\text{move}}(N))
1	0	0	0
2	1	(2\cdot1-2+1=1)	(2\cdot1-2+2=2)
3	2	(3\cdot2-4+1=3)	(3\cdot2-4+3=5)
4	2	(4\cdot2-4+1=5)	(4\cdot2-4+4=8)
5	3	(5\cdot3-8+1=8)	(5\cdot3-8+5=12)

• (N=3): split into 2 and 1. Sorting 2 costs 1 comparison, sorting 1 costs 0, merging 2 and 1 costs (2+1-1=2) comparisons → total 3. Moves: 2 + 0 + 3 = 5.
• (N=4): split into 2 and 2. Each half costs 1 comparison, merge costs 3 → 5. Moves: 2 + 2 + 4 = 8.

The inductive proof already verifies the closed form for all (N\ge 1). The formulas are therefore correct.