Как отсортировать матрицу amxn, в которой все m строк отсортированы и n столбцов отсортированы?

Дана матрица с m строками и n столбцами, каждая из которых сортируется. Как эффективно отсортировать всю матрицу?

Я знаю решение, которое выполняется за O (mn log (min (m, n)). Я ищу лучшее решение.

Подход, который я знаю, в основном требует 2 строк / столбцов и применяет операцию слияния.

Вот пример:

[[1,4,7,10],

 [2,5,8,11],

 [3,6,9,12]]

- это входной мартикс, в котором отсортированы все строки и столбцы.

Ожидаемый результат:

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

Другой пример:

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