How to sort a m x n matrix which has all its m rows sorted and n columns sorted?

Question

Given a matrix with m rows and n columns, each of which are sorted. How to efficiently sort the entire matrix?

I know a solution which runs in O(m n log(min(m,n)). I am looking for a better solution.

The approach that I know basically takes 2 rows/cols at a time and applies merge operation.

Here is an example:

[[1,4,7,10],

 [2,5,8,11],

 [3,6,9,12]]

is the input martix which has every row and column sorted.

Expected output is:

[1,2,3,4,5,6,7,8,9,10,11,12]

Another example:

[[1, 2, 3, 3, 4, 5, 6, 6, 7, 7],

 [1, 2, 4, 6, 7, 7, 8, 8, 9,10],

 [3, 3, 4, 8, 8, 9,10,11,11,12],

 [3, 3, 5, 8, 8, 9,12,12,13,14]]

Answer 1

I don't think you can do it any faster than Ω(m n log(min(m, n)), at least not in the general case.

Suppose (without loss of generality) that m < n. Then your matrix looks like this:

Each circle is a matrix entry and each arrow indicates a known order relation (the entry at the source of the arrow is smaller than the entry at the destination of the arrow).

To sort the matrix, we must resolve all the unknown order relations, some of which are shown in the grey boxes here:

Sorting all of these boxes takes:

2 Σ_{k < m} Ω(k log k) + (n - m + 1) Ω(m log m)

= 2 Ω(m² log m) + (n - m + 1) Ω(m log m)

= Ω(m n log m)