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

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?

• As an aside, it irritates me when we see claims that "sorting is $\Omega(n\log n)$" but that do not specify the input model and the model of computation. Comparison sorting is $\Omega(n\log n)$. Sorting, in general, may be faster than that, for instance for strings (if $n$ is the total input length) or integers (in certain models of computation that allow constant time integer arithmetic operations). – David Eppstein Feb 9 '13 at 21:03
• To be even more pedantic: Comparison sorting is not $\Omega(n\log n)$, because comparison sorting isn't a function from $\mathbb{R}$ to $\mathbb{R}$. Sorting requires $\Omega(n\log n)$ time in any binary decision tree model (not just comparisons). – Jeffε Feb 9 '13 at 22:43

## 1 Answer

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.

• Again, in any binary decision tree model, not just comparisons. – Jeffε Feb 9 '13 at 22:46