8-7 The $0$-$1$ sorting lemma and columnsort

A compare-exchange operation on two array elements $A[i]$ and $A[j]$, where $i < j$, has the form

COMPARE-EXCHANGE(A, i, j)
    if A[i] > A[j]
        exchange A[i] with A[j]

After the compare-exchange operation, we know that $A[i] \le A[j]$.

An oblivious compare-exchange algorithm operates solely by a sequence of prespecified 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:

INSERTION-SORT(A)
    for j = 2 to A.length
        for i = j - 1 downto 1
            COMPARE-EXCHANGE(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 $0$s and $1$s, then it correctly sorts all inputs containing 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 $\text X$ fails to correctly sort the array $A[1..n]$. Let $A[p]$ be the smallest value in $A$ that algorithm $\text X$ puts into the wrong location, and let $A[q]$ be the value that algorithm $\text X$ moves to the location into which $A[p]$ should have gone. Define an array $B[1..n]$ of $0$s and $1$s as follows:

$$ B[i] = \begin{cases} 0 & \text{if $A[i] \le A[p]$}, \\ 1 & \text{if $A[i] > A[p]$}. \end{cases} $$

a. Argue that $A[q] > A[p]$, so that $B[p] = 0$ and $B[q] = 1$.

b. To complete the proof of the $0$-$1$ sorting lemma, prove that algorithm $\text X$ fails to sort array $B$ correctly.

Now 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 = rs$), subject to three restrictions:

  • $r$ must be even,
  • $s$ must be a divisor of $r$, and
  • $r \ge 2 s^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:

  1. Sort each column.
  2. 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.
  3. Sort each column.
  4. Perform the inverse of the permutation performed in step 2.
  5. Sort each column.
  6. Shift the top half of each column into the bottom half of the same column, and shift 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.
  7. Sort each column.
  8. Perform the inverse of the permutation performed in step 6.

Figure 8.5 shows an example of the steps of columnsort with $r = 6$ and $s = 3$. (Even though this example violates the requirement that $r \ge 2s^2$, it happens to work.)

c. 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.

Although it might seem hard to believe 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 that an area of an array is clean if we know that it contains either all $0$s or all $1$s. Otherwise, the area might contain mixed $0$s and $1$s, and it is dirty. From here on, assume that the input array contains only $0$s and $1$s, and that we can treat it as an array with $r$ rows and $s$ columns.

d. Prove that after steps 1–3, the array consists of some clean rows of $0$s at the top, some clean rows of $1$s at the bottom, and at most $s$ dirty rows between them.

e. Prove that after step 4, the array, read in column - major order, starts with a clean area of $0$s, ends with a clean area of $1$s, and has a dirty area of at most $s^2$ elements in the middle.

f. Prove that steps 5–8 produce a fully sorted $0$-$1$ output. Conclude that columnsort correctly sorts all inputs containing arbitrary values.

g. Now suppose that $s$ does not divide $r$. Prove that after steps 1–3, the array consists of some clean rows of $0$s at the top, some clean rows of $1$s 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. Suggest a simple change to step 1 that allows us to maintain the requirement that $r \ge 2s^2$ even when $s$ does not divide $r$, and prove that with your change, columnsort correctly sorts.

(Removed)