Sorting rows then sorting columns preserves the sorting of rows

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$:

$\cdots \quad a \quad d \quad \cdots_1$

$\cdots \quad b \quad c \quad \cdots_2$

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:

$\cdots \quad a \quad c \quad \cdots_2$

$\cdots \quad b \quad d \quad \cdots_1$

And the invariance is preserved since $a \le c$ and $b \le d$. Look! No index chasing!