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 &amp; 4 &amp; 1 \\
3 &amp; 5 &amp; 6 \\
7 &amp; 9 &amp; 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 &lt; 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$