k-Sorted Matrix

Sorting a nearly ordered matrix

Problem Statement

You have an m×n integer matrix M. Each row is k-sorted, meaning every element in that row is at most k positions away from where it would be if you sorted the row in non-decreasing order. Your goal is to rearrange all elements so that the matrix is sorted in row-major order—the smallest elements fill the first row left to right, then th…