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!