Sort Every Matrix Row and Column Without Losing Order

Sorting every row and column is not the same as sorting all nine elements globally

For the matrix [[8, 3, 7], [4, 9, 1], [6, 2, 5]], the required result has two conditions at once: values do not decrease from left to right inside any row, and values do not decrease from top to bottom inside any column. You are ordering each row and each column, not creating one long sorted list.

If you flatten the matrix into [8, 3, 7, 4, 9, 1, 6, 2, 5], sort all nine values, and fill the matrix row by row, you get [[1, 2, 3], [4, 5, 6], [7, 8, 9]]. That result does satisfy both conditions for this example, but global sorting solves a stronger and different problem. The row and column method sorts values within their existing directions, using one row at a time and then one column at a time.

Checking only the rows is not enough. The row-sorted state [[3, 7, 8], [1, 4, 9], [2, 5, 6]] has every row in ascending order, but its first column is 3, 1, 2, which is not nondecreasing. The column phase is needed to establish the second condition.

Sorting the columns after the rows keeps every row sorted

Start by sorting each row of [[8, 3, 7], [4, 9, 1], [6, 2, 5]] in ascending order. The matrix becomes [[3, 7, 8], [1, 4, 9], [2, 5, 6]]. Now sort the first column, then the second, then the third. The result is [[1, 4, 6], [2, 5, 8], [3, 7, 9]].

The important fact is that column sorting moves complete values between rows, but it does not change the order of positions inside any one row. Before column sorting, every value in a row is at least as large as the value to its left. After sorting corresponding columns, the same left-to-right relationships remain true for this matrix, while each column also becomes nondecreasing from top to bottom. Thus column sorting completes the second direction without destroying the first.

A temporary array turns each column into something the library can sort

A row is already stored as an array, so you can pass that row directly to the sorting library. A column is spread across different rows, so you first copy one column into a reusable temporary array. Sort the temporary array, then write its values back into that same column. Repeat this for column 0, column 1, and column 2.

#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<vector<int>> matrix = {
        {8, 3, 7},
        {4, 9, 1},
        {6, 2, 5}
    };

    int rows = matrix.size();
    int cols = matrix[0].size();

    for (int r = 0; r < rows; r++) {
        sort(matrix[r].begin(), matrix[r].end());
    }

    vector<int> temp(rows);
    for (int c = 0; c < cols; c++) {
        for (int r = 0; r < rows; r++) {
            temp[r] = matrix[r][c];
        }

        sort(temp.begin(), temp.end());

        for (int r = 0; r < rows; r++) {
            matrix[r][c] = temp[r];
        }
    }

    return 0;
}

import java.util.Arrays;

class Main {
    public static void main(String[] args) {
        int[][] matrix = {
            {8, 3, 7},
            {4, 9, 1},
            {6, 2, 5}
        };

        int rows = matrix.length;
        int cols = matrix[0].length;

        for (int r = 0; r < rows; r++) {
            Arrays.sort(matrix[r]);
        }

        int[] temp = new int[rows];
        for (int c = 0; c < cols; c++) {
            for (int r = 0; r < rows; r++) {
                temp[r] = matrix[r][c];
            }

            Arrays.sort(temp);

            for (int r = 0; r < rows; r++) {
                matrix[r][c] = temp[r];
            }
        }
    }
}

For the first column after row sorting, the temporary array receives [3, 1, 2]. Sorting it produces [1, 2, 3], which is written back into matrix[0][0], matrix[1][0], and matrix[2][0]. The same extraction, sorting, and write-back process handles the next two columns. The column index stays fixed during extraction, while the row index changes.

temp[?] = matrix[?][1];

The two sorting phases determine both the cost and the final guarantee

Sorting R rows of length C costs O(R * C log C), because each row is sorted independently. Sorting C columns of length R costs O(C * R log R). Together, the time complexity is O(R * C log C + C * R log R). For the 3 x 3 running matrix, this means three sorts of length 3 in the row phase and three sorts of length 3 in the column phase.

The temporary array holds one complete column, so its length is R. Reusing it for every column gives O(R) temporary space. The matrix itself is not counted as temporary space here, because it is the input being transformed. After the final write-back, every row is nondecreasing from left to right and every column is nondecreasing from top to bottom.

Repeated values do not change the method. Equal values may exchange positions during sorting, but nondecreasing order allows adjacent values to be equal. A one-row matrix has no meaningful vertical comparison, and the row phase still sorts its only row. A one-column matrix has no left-to-right comparison, and the column phase still sorts its only column. The same loops handle both shapes without a special sorting rule.