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?
Best Answer
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)$.