From Peter Winkler's book:
Given a matrix, prove that after first sorting each row, then sorting each column, each row remains sorted.
For example: starting with
$$\begin{bmatrix}
1 & -3 & 2 \\
0 & 1 & -5 \\
4 & -1 & 1
\end{bmatrix}$$
Sorting each row individually and in ascending order gives
$$\begin{bmatrix}
-3 & 1 & 2 \\
-5 & 0 & 1 \\
-1 & 1 & 4
\end{bmatrix}$$
Then sorting each column individually in ascending order gives
$$\begin{bmatrix}
-5 & 0 & 1 \\
-3 & 1 & 2 \\
-1 & 1 & 4
\end{bmatrix}$$
And notice the rows are still individually sorted, in ascending order.
I was trying to find a 'nice' proof that does not involve messy index comparisons… but I cannot find one!
Best Answer
Notice that you can start from after the first step. Specifically, you only need to prove that, given an arbitrary matrix where each row is already in ascending order, sorting each column in ascending order keeps each row sorted. Here is a very neat trick to do this.
Let $m$ be the number of columns. For each $k$ from $1$ to $m$, sort the rows of the subarray from column $k$ to column $m$ in increasing order of the element in column $k$. (Each row of the subarray stays together.) We do this sorting by bubble sort. We maintain the invariant that the elements in each row stays sorted. This invariant is trivially true when $k = 1$. When $k > 1$, and we perform a swap involving rows $p$ and $(p+1)$, consider the elements in those rows and in the columns $(k-1)$ and $k$:
By the invariance we have $a \le b \le c$ and the swap is only done because $c \le d$. After the swap we have:
And the invariance is preserved since $a \le c$ and $b \le d$. Look! No index chasing!