If we sort a table column-wise and then row-wise why the table is still sorted column-wise?

Say we have a $n \times n$ table which elements are sorted column-wise, for example:

$$
\left( \begin{array}{ccc}
2 & 4 & 1 \\
3 & 5 & 6 \\
7 & 9 & 8 \end{array} \right)
$$

I would like to prove that if we sort this table row-wise, it will be still sorted column-wise.

This is one of the steps to prove the shell sort correctness.

Consider some column $i$ and some rows $j < k$. Let $x$ be the element at row $j$ column $i$ after the final sorting, and let $y$ be the element at row $k$ column $i$. We want to prove that $x \leq y$.

Since $x$ ended up in column $i$, there must have been $n-i$ elements in row $j$ larger than $x$. Together with $x$ itself, these are $n-i+1$ elements in row $j$ that were at least as large as $x$. The corresponding elements in row $k$ were also at least as large as $x$, since the columns were sorted. Summarizing, row $k$ contains at least $n-i+1$ elements which are at least as large as $x$. That means that after sorting, the element at position $i$ on row $k$ (that is, $y$) is at least as large as $x$

StackExchange Computer Science Q#48405, answer score: 4