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:
- we can get a sorted list of the $n^2$ elements from the sorted matrix in $O(n^2)$ http://math.stackexchange.com/questions/298191/lower-bound-for-matrix-sorting/298199?iemail=1#298199
- you can't get a sorted list from the matrix faster than $Ω(n^2\log(n))$ http://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?