Design an algorithm to sort a given m x n matrix such that aach row of the matrix is sorted in ascending order. The last element of any row i is less than or equal to the first element of the next row i+1.

Hint

To sort a matrix in strict order, we merge all entries of the matrix into a single array. Sort the array, and then split the array back to n x m matrix.

# Python implementation

matrix = [
  [ 1, 4, 7 ],
  [ 2, 5, 8 ],
  [ 3, 6, 9 ]
]
output = []
h = len(matrix)
w = len(matrix[0])

ls = []

for y in matrix:
  ls += y

ls.sort()

for i in range(h):
  output.append(ls[i * w:i * w + w])

print(output)

// Javascript implementation

const matrix = [
  [ 1, 4, 7 ],
  [ 2, 5, 8 ],
  [ 3, 6, 9 ]
];
const output = [];
const h = matrix.length;
const w = matrix[0].length;

const list = matrix.reduce((cum, i) => {
  return [...cum, ...i];
}, []);

list.sort();

for (let i = 0; i < h; i++) {
  output.push(list.slice(i * w, i * w + w ));
}

console.log(output);

Sort matrix in a strict order

Hint