Can we get a sorted list from a sorted matrix in $O(n^2)$

Question

I'm confused. I want to prove that that the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order is $\Omega(n^2\log n)$. I proceed by assuming that it can be done faster than $n^2\log n$ and try to violate the $\log(m!)$ lower bound for comparisons needed to sort m elements. I have two conflicting answers:

1. we can get a sorted list of the $n^2$ elements from the sorted matrix in $O(n^2)$ https://math.stackexchange.com/questions/298191/lower-bound-for-matrix-sorting/298199?iemail=1#298199
2. you can't get a sorted list from the matrix faster than $Ω(n^2\log(n))$ https://stackoverflow.com/questions/4279524/how-to-sort-a-m-x-n-matrix-which-has-all-its-m-rows-sorted-and-n-columns-sorted

Which one is right?

Answer 1

The lower bound is correct (2) - you can not do this better than $\Omega(n^2 \log n)$ and (1) is of course wrong. Lets us first define what is a sorted matrix - it is a matrix where the elements in each row and column are sorted in increasing order.

It is now easy to verify that each diagonal might contains elements that are in any arbitrary order - you just need to make them sufficiently large. In particular, sorting the matrix implies sorting each one of these diagonals. The $i$th diagonal has $i$ entries, and as such $i!$ possible ordering. As such, a sorted matrix could define at least $X = \prod_{i=1}^n i!$ different orderings. It is now easy to verify that $\log_2 X = \Omega(n^2 \log n)$, implying that in the comparison model (and as Jeff points out below, in any binary decision tree model) at least this is a lower bound on the sorting time.