TAOCP 5.2.2 Exercise 11

Section 5.2.2: Sorting by Exchanging

Exercise 11. ▶ [M25] Which permutation of ${1, 2, \ldots, 16}$ maximizes the number of exchanges done by Batcher's algorithm?

Verified: no
Solve time: 15m08s

Solution

Batcher's merge-exchange sort for (n = 16) is an odd-even merge sort. The sorting network consists of (63) compare‑exchange operations (comparators). The maximum possible number of exchanges is (63), attained exactly when every comparator finds its two inputs in decreasing order and therefore swaps them. Such an input permutation is unique and can be obtained by running the network backwards from the sorted output (1,2,\dots,16): each comparator is replaced by an unconditional swap of the same two positions, and the swaps are applied in the reverse order of the forward network.

The forward network is generated by the standard recursive odd‑even merge sort:

• (\text{sort}(lo, n, r)): if (n>1) then
  (\text{sort}(lo, n/2, r));
  (\text{sort}(lo + n r/2, n/2, r));
  (\text{merge}(lo, n, r)).

• (\text{merge}(lo, n, r)): if (n=2) then compare‑exchange((lo,, lo+r));
  else
  (\text{merge}(lo, n/2, 2r));
  (\text{merge}(lo+r, n/2, 2r));
  for (i = 1) to (n/2-1) do compare‑exchange((lo + (2i-1)r,, lo + 2i r)).

Starting with (\text{sort}(1, 16, 1)) and using a depth‑first, left‑to‑right execution order yields the following (63) comparators in forward sequence (each pair ((i,j)) means compare (K_i) and (K_j) with (i<j)):

[ \begin{array}{lllll} 1.;(1,2) & 2.;(3,4) & 3.;(1,3) & 4.;(2,4) & 5.;(2,3) \ 6.;(5,6) & 7.;(7,8) & 8.;(5,7) & 9.;(6,8) & 10.;(6,7) \ 11.;(1,5) & 12.;(3,7) & 13.;(3,5) & 14.;(2,6) & 15.;(4,8) \ 16.;(4,6) & 17.;(2,3) & 18.;(4,5) & 19.;(6,7) & 20.;(9,10) \ 21.;(11,12) & 22.;(9,11) & 23.;(10,12) & 24.;(10,11) & 25.;(13,14) \ 26.;(15,16) & 27.;(13,15) & 28.;(14,16) & 29.;(14,15) & 30.;(9,13) \ 31.;(11,15) & 32.;(11,13) & 33.;(10,14) & 34.;(12,16) & 35.;(12,14) \ 36.;(10,11) & 37.;(12,13) & 38.;(14,15) & 39.;(1,9) & 40.;(5,13) \ 41.;(5,9) & 42.;(3,11) & 43.;(7,15) & 44.;(7,11) & 45.;(3,5) \ 46.;(7,9) & 47.;(11,13) & 48.;(2,10) & 49.;(6,14) & 50.;(6,10) \ 51.;(4,12) & 52.;(8,16) & 53.;(8,12) & 54.;(4,6) & 55.;(8,10) \ 56.;(12,14) & 57.;(2,3) & 58.;(4,5) & 59.;(6,7) & 60.;(8,9) \ 61.;(10,11) & 62.;(12,13) & 63.;(14,15) \end{array} ]

Reversing this list and applying each comparator as an unconditional swap to the initially sorted array ([1,2,\dots,16]) gives the desired permutation. Carrying out the (63) reverse swaps step by step yields the final array:

[ [16,;10,;13,;5,;14,;8,;11,;2,;15,;6,;9,;3,;12,;4,;7,;1]. ]

This permutation forces every one of the (63) comparators to perform an exchange, which is the maximum possible.

[ \boxed{16,;10,;13,;5,;14,;8,;11,;2,;15,;6,;9,;3,;12,;4,;7,;1} ] ∎