CLRS 8-7 The 0-1 Sorting Lemma and Column Sort: A compare-exchange operation on two array elements A[i] and A[j], where i < j, has the form CompareExchange(A, i, j) if A[i] > A[j] then exchange A[i] with A[j] After the compare-xchange operation, we know that A[i] A[j]. An oblivious compare-exchange algorithm operates solely by a sequence of pre-specified compare-exchange operations. The indices of the positions compared in the sequence must be determined in advance, and although they can depend on the number of elements being sorted, they cannot depend on the values being sorted, nor can they depend on the result of any prior compare-exchange operation. For example, here is insertion sort expressed as an oblivious compare-exchange algorithm: InsertionSort(A) for j 2 to A.length do for i j 1 downto 1 do CompareExchange(A, i, i + 1) The 0-1 sorting lemma provides a powerful way to prove that an oblivious compare-exchange algorithm produces a sorted result. It states that if an oblivious compare-exchange algorithm correctly sorts all input sequences consisting of only 0s and 1s, then it correctly sorts all inputs comtaining arbitrary values. You will prove the 0-1 sorting lemma by proving its contrapositive: if an oblivious compare-exchange

algorithm fails to sort an input containing arbitrary values, then it fails to sort some 0-1 input. Assume that an oblivious compare-exchange algorithm X fails to correctly sort the array A[1..n]. Let A[p] be the smallest value in A that X puts into the wrong location, and let A[q] be the value that algorithm X moves to the location into which A[p] should have gone. Define array B[1..n] of 0s and 1s as follows: B[i] = { 0 if A[i] A[p] 1 if A[i] > A[p] . After you prove the 0-1 sorting lemma (in step (b) below), you will use the 0-1 sorting lemma to prove that a particular sorting algorithm works correctly. The algorithm columnsort works on a rectangular array of n elements. The array has r rows and s columns (so that n = r s), subject to three restrictions r must be even, s must be a divisor of r, and r 2s 2 . When columnsort completes, the array is sorted in column-major order : reading down the columns, from left to right, the elements monotonically increase. Columnsort operates in eight steps, regardless of the value of n. The odd steps are all the same: sort each column individually. Each even step is a fixed permutation. Here are the steps: Sort each column. Transpose the array, but reshape it back to r rows and s columns. In other words, turn the leftmost column into the top r/s rows, in order; turn the next column into the next r/s rows, in order; and so on. Sort each column. Perform the inverse of the permutation performed in the second step. Sort each column. Shift the top half of each column into the bottom half of the same column, and shif the bottom half of each column into the top half of the next column to the right. Leave the top half of the leftmost column empty. Shift the bottom half of the last column into the top half of a new rightmost column, and leave the bottom half of this new column empty. Sort each column. Perform the inverse of the permutation in the sixth step. Figure 1 shows an example of the steps of columnsort with r = 6 and s = 3. Even though this example

violates the requirement that r 2s 2 , it happens to work. Although it might seem hard to beleve that columnsort actually sorts, you will use the 0-1 sorting lemma to prove that it does. The 0-1 sorting lemma applies because we can treat columnsort as an oblivious compare-exchange algorithm. A couple of definitions will help you apply the 0-1 sorting lemma. We say an area of an array is clean if we know that it contains either all 0s or all 1s. Otherwise, the area might contain mixed 0s and 1s, in which case it is dirty. From part (d) on, assume that the input array contains only 0s and 1s and that we can treat it as an array with r rows and s columns. (a) [4 points] Argue that A[q] > A[p] so that B[p] = 0 and B[q] = 1. (b) [4 points] To complete the proof of the 0-1 sorting lemma, prove that algorithm X fails to sort the array B correctly. (c) [4 points] Argue that we can treat columnsort as an oblivious compare-exchange algorithm, even if we do not know what sorting method the odd steps use. 2 Figure 1: Example Execution of Columnsort 10 14 5 8 7 17 12 1 6 16 9 11 4 15 2 18 3 13 4 1 2 8 3 5 10 7 6 12 9 11 16 14 13 18 15 17 4 8 10 12 16 18 1 3 7 9 14 15 2 5 6 11 13 17 1 3 6 2 5 7 4 8 10 9 13 15 11 14 17 12 16 18 1 4 11 3 8 14 6 10 17 2 9 12 5 13 16 7 15 18 Input Step 1 Step 2 Step 3 Step 4 1 4 11 2 8 12 3 9 14 5 10 16 6 13 17 7 15 18 5 10 16 6 13 17 7 15 18 1 4 11 2 8 12 3 9 14 4 10 16 5 11 17 6 12 18 1 7 13 2 8 14 3 9 15 1 7 13 2 8 14 3 9 15 4 10 16 5 11 17 6 12 18 Step 5 Step 6 Step 7 Step 8

(d) [4 points] Prove that after the first three steps, the array consists of some clean rows of 0s at the top, some clean rows of 1s at the bottom, and at most s dirty rows between them. (e) [4 points] Prove that after the fourth step the array, read in column-major order, starts with a clean area of 0s, ends with a clean area of 1s, and has a dirty area of at most s 2 elements in the middle. (f) [5 points] Prove that steps five through eight produce a fully sorted 0-1 output. Conclude that columnsort correctly sorts all inputs containing arbitrary values. (g) [5 points] Now suppose that s does not divide r. Prove that after steps one through three, the array consists of some clean rows of 0s at the top, some clean rows of 1s at the bottom, and at most 2s 1 dirty rows between them. How large must r be, compared with s, for columnsort to correctly sort when s does not divide r. (h) [5 points] Suggest a simple change to step one that allows us to maintain the requirement that r 2s 2 even when s does not divide r, and prove that with your change, columnsort correctly sorts