# Lower bound for matrix sorting?

Consider the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order. I want to find the lower and upper bound of this problem.

I found that it is $O(n^2logn)$ by just sorting the elements and then outputting the first $n$ elements as the first row, the next $n$ elements as the second row, and so on. However, I want to prove that it is also $\Omega(n^2logn)$.

After trying smaller examples, I think I should prove that if I can solve this problem using less than $n^2log(\frac{n}{e})$ comparisons, it would violates the $log(m!)$ lower bound for comparisons needed to sort $m$ elements. Any ideas on how to prove that?

-

Here is the argument I alluded to in my earliest comment. I claim that a sorted $n\times n$ matrix $A$ can be linearly sorted in $n^2 \log_2 n + O(n^2)$ comparisons. To do this, we maintain a vector $v$ which records up to $n$ values of $A$ in increasing order (and their corresponding locations $i,j$). Initially, take $v$ to be the first row of $A$.

We then iterate the following procedure $n^2$ times: output the least value of $v$, delete it from $v$, and insert into $v$ the entry directly underneath it in $A$ (if there is one). Since $v$ is sorted, finding the lowest value takes $0$ comparisons, but insertion of the new value requires a binary search on $v$, which is $\lceil \log_2 m \rceil \le \log_2 m + 1$ comparisons, where $m \le n$ is the length of $v$.

It should be clear that we never insert any value into $v$ before exhausting all smaller values, so if we iterate $n^2$ times this gives a linearly sorted list. The number of comparisons is at most $n^2 (\log_2 n + 1) = n^2 \log_2 n + O(n^2)$, proving the claim.

However, to sort an arbitrary matrix of $n^2$ elements requires at least $\log_2(n^2!)$ comparisons in the worst case, and this is equal to $n^2 \log_2 n^2 - O(n^2) = 2n^2 \log_2 n - O(n^2)$ . Therefore, getting from an arbitrary matrix to a sorted matrix must consume at least the difference of these two amounts of comparisons in the worst case, namely $n^2 \log_2 n - O(n^2)$.

-
I don't understand your conclusion (Therfore, ... ). How do you go from the problem of sorting the elements of a sorted matrix to the problem of sorting the matrix itself. Please, can you explain it to me? –  J Mint Feb 9 '13 at 9:41
@jiji777 Do you understand what the lower bound for sorting means? There is no comparison-based way to sort $n^2$ numbers without spending about $2n^2 \log n$ comparisons. Yet if we could matrix-sort cheaply it would only cost about half that many. –  Erick Wong Feb 9 '13 at 15:00
No, I understand that. But if T(n) is the time spent to get from an arbitrary matrix to a sorted matrix and S(n) is the time spent to get from a sorted matrix to a sorted array. Shouldn't you prove that $S(n)$ cannot be done in less than $n^2logn$ to prove that $T(n) \geq n^2logn+log(n^2!)$. Is giving one algorithm that runs in $n^2logn$ sufficient or do we have to prove it for all algorithms? –  J Mint Feb 9 '13 at 20:21
@jiji777 You have it backwards. We know that $T(n) + S(n) \ge 2n^2 \log n$, because the RHS is how long it takes to go from arbitrary matrix to sorted list, and the LHS is one possible way of doing so. A lower bound for $S(n)$ wouldn't help at all to control $T(n)$. –  Erick Wong Feb 9 '13 at 20:23
right. Ok, thanks. –  J Mint Feb 9 '13 at 20:26