<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-02-09T22:46:10.633Z
Again, in _any_ binary decision tree model, not just comparisons.
Jeffε
CC BY-SA 3.0
2013-02-09T16:21:17.517Z
2013-02-10T04:21:39.783Z
2013-02-10T04:21:39.783Z
Sariel Har-Peled
<p>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:</p>

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

<p>Which one is right?</p>

CC BY-SA 3.0
2013-02-09T21:03:21.437Z
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
CC BY-SA 3.0
2013-02-09T22:43:20.787Z
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ε
<time-complexity><lower-bounds><matrices><sorting><asymptotics>
Can we get a sorted list from a sorted matrix in $O(n^2)$
user2038833
# Can we get a sorted list from a sorted matrix in $O(n^2)$

(Asked by: username_0 on 2013-02-09)

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?

**Tags:** time-complexity, lower-bounds, matrices, sorting, asymptotics
> **Comments:**
> **username_1**: 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).  
> **username_2**: 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).  

---

## 1 answers

### Answer by username_3 on 2013-02-09. Score: 15 | Accepted 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.

> **Comments:**
> **username_2**: Again, in _any_ binary decision tree model, not just comparisons.  

---

