小编典典

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

algorithm

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]]

阅读 235

收藏
2020-07-28

共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:

a matrix with rows and columns sorted

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:

the order relations remaining to be
resolved

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 )

2020-07-28