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

1
2
3
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:

1
2
3
4
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.

a. $A[q]$ must go the wrong place, because it goes where $A[p]$ should go. Since $A[p]$ is the smallest value in array $A$ that goes to the wrong array location, $A[p]$ must be smaller than $A[q]$.

b. From how we have defined the array $B$, we have that if $A[i] \le A[j]$ then $B[i] \le B[j]$. Therefore, algorithm $\text X$ performs the same sequence of exchanges on array $B$ as it does on array $A$. The output produced on array $A$ is of the form $\ldots A[q] \ldots A[p] \ldots$, and so the output produced on array $B$ is of the form $\ldots B[q] \ldots B[p] \ldots$, or $\ldots 1 \ldots 0 \ldots$. Hence algorithm $\text X$ fails to sort array $B$ correctly.

c. The even steps perform fixed permutations. The odd steps sort each column by some sorting algorithm, which might not be an oblivious compare-exchange algorithm. But the result of sorting each column would be the same as if we did use an oblivious compare-exchange algorithm.

d. After step 1, each column has $0$s on top and $1$s on the bottom, with at most one transition between $0$s and $1$s, and it is a $0 \to 1$ transition. (As we read the array in column - major order, all $1 \to 0$ transitions occur between adjacent columns.) After step 2, therefore, each consecutive group of $r / s$ rows, read in row-major order, has at most one transition, and again it is a $0 \to 1$ transition. All $1 \to 0$ transitions occur at the end of a group of $r / s$ rows. Since there are s groups of $r / s$ rows, there are at most $s$ dirty rows, and the rest of the rows are clean. Step 3 moves the $0$s to the top rows and the $1$s to the bottom rows. The $s$ dirty rows are somewhere in the middle.

e. The dirty area after step 3 is at most $s$ rows high and $s$ columns wide, and so its area is at most $s^2$. Step 4 turns the clean $0$s in the top rows into a clean area on the left, the clean $1$s in the bottom rows into a clean area on the right, and the dirty area of size $s^2$ is between the two clean areas.

f. First, we argue that if the dirty area after step 4 has size at most $r / 2$, then steps 5–8 complete the sorting. If the dirty area has size at most $r / 2$ (half a column), then it either resides entirely in one column or it resides in the bottom half of one column and the top half of the next column. In the former case, step 5 sorts the column containing the dirty area, and steps 6–8 maintain that the array is sorted. In the latter case, step 5 cannot increase the size of the dirty area, step 6 moves the entire dirty area into the same column, step 7 sorts it, and step 8 moves it back.

Second, we argue that the dirty area after step 4 has size at most $r / 2$. But that follows immediately from the requirement that $r \ge 2s^2$ and the property that after step 4, the dirty area has size at most $s^2$.

g. If $s$ does not divide $r$, then after step 2, we can see up to $s$ $0 \to 1$ transitions and $s - 1$ $1 \to 0$ transitions in the rows. After step 3, we would have up to $2s - 1$ dirty rows, for a dirty area size of at most $2s^2 - s$. To push the correctness proof through, we need $2s^2 - s \le r / 2$, or $r \ge 4s^2 - 2s$.

h. We can reduce the number of transitions in the rows after step 2 back down to at most $s$ by sorting every other column in reverse order in step 1. Now if we have a transition (either $1 \to 0$ or $0 \to 1$) between columns after step 1, then either one of the columns had all $1$s or the other had all $0$s, in which case we would not have a transition within one of the columns.