Sort All Elements of a Matrix in Ascending Order

The standard approach to sorting all elements of an M×N matrix has three steps: flatten the matrix into a 1D array, sort that array, then write the sorted values back row by row.

That’s the entire algorithm. Everything else is implementation detail and edge-case handling.

The Flatten-Sort-Refill Algorithm

The key insight is that a 2D matrix stored in row-major order is a 1D array with index arithmetic layered on top. Python’s list of lists hides this, but the flatten step exposes it. Once the data is flat, any standard sort applies without modification. The refill step is the reverse: take the sorted 1D array and write it back into a 2D structure using the column count as the stride.

Given a matrix of M rows and N columns, the steps are:

• Step 1: Allocate a 1D array of M×N integers.
• Step 2: Copy every matrix element into the 1D array in row-major order (row 0 first, then row 1, and so on).
• Step 3: Sort the 1D array. Python’s built-in sort() method uses Timsort; C’s qsort from <stdlib.h> uses a hybrid sort.
• Step 4: Write the sorted values back into the matrix in row-major order, N elements per row.

The time cost: flattening is O(M×N), sorting is O(M×N log(M×N)), refilling is O(M×N). The sort step dominates, giving a total of O(M×N log(M×N)). The extra space is O(M×N) for the intermediate 1D array (the in-place variant reduces this to O(1), covered in the tradeoff section below).

Python implementation

def sort_matrix(matrix):
    if not matrix or not matrix[0]:
        return matrix  # empty-matrix guard
    m = len(matrix)
    n = len(matrix[0])
    flat = [matrix[i][j] for i in range(m) for j in range(n)]
    flat.sort()
    idx = 0
    for i in range(m):
        for j in range(n):
            matrix[i][j] = flat[idx]
            idx += 1
    return matrix

C implementation

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

void sort_matrix(int matrix[][3], int m, int n) {
    int arr[m * n];
    int k = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            arr[k++] = matrix[i][j];
    qsort(arr, m * n, sizeof(int), compare);
    k = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            matrix[i][j] = arr[k++];
}

For the full qsort signature and comparator contract, see the cppreference qsort documentation.

Worked Example: A 3×3 Matrix

Starting matrix (a standard placement-round test case):

 9   7   5
 2   8   6
10   3   1

Walk through each step from first principles:

• Step 1 — Flatten: Read row 0 left to right, then row 1, then row 2. The 1D array is [9, 7, 5, 2, 8, 6, 10, 3, 1]. Total: 9 elements for a 3×3 matrix.
• Step 2 — Sort: Apply any comparison sort to the 9-element array. Sorted result: [1, 2, 3, 5, 6, 7, 8, 9, 10].
• Step 3 — Refill: Write back in row-major order, 3 elements per row (N = 3):
  • Row 0 receives indices 0..2: [1, 2, 3]
  • Row 1 receives indices 3..5: [5, 6, 7]
  • Row 2 receives indices 6..8: [8, 9, 10]

Final matrix:

 1   2   3
 5   6   7
 8   9  10

Verification: within each row, elements are in ascending order. Across rows, the first element of row 1 (5) is greater than the last element of row 0 (3). The first element of row 2 (8) is greater than the last element of row 1 (7). This is the globally sorted condition the problem asks for.

A useful cross-check: the minimum element in the original matrix is 1 and the maximum is 10. After flatten-sort-refill, the minimum always lands at position (0, 0) and the maximum at position (M-1, N-1). For a 3×3 matrix those positions are (0, 0) and (2, 2). Both hold 1 and 10 respectively in the result above, confirming the sort is globally correct.

Row-Wise Sort Variant

Row-wise sort is a different operation. It sorts each row independently, with no guarantee about how adjacent rows relate to each other:

def sort_matrix_rowwise(matrix):
    for row in matrix:
        row.sort()
    return matrix

Applied to the same 3×3 matrix:

• Row 0 [9, 7, 5] sorted: [5, 7, 9]
• Row 1 [2, 8, 6] sorted: [2, 6, 8]
• Row 2 [10, 3, 1] sorted: [1, 3, 10]

Row-wise result:

 5   7   9
 2   6   8
 1   3  10

This result is not globally sorted. The first element of row 1 (2) is less than the last element of row 0 (9). Two takeaways:

• Placement problems that ask for globally sorted output require the flatten-sort-refill approach.
• Problems that ask for each row to be sorted in ascending order want the row-wise variant.

Read the problem statement carefully. The two outputs are distinct and the difference is testable.

When row-wise sort is the right answer

Row-wise sort is not always wrong. It is the correct answer when each row represents an independent dataset that must stay intact as a unit. Suppose the matrix stores each student’s test scores across multiple subjects, one student per row. Sorting each row puts that student’s scores in ascending order without mixing scores across students. A global flatten-sort would merge all students’ scores together, destroying the row-to-student mapping entirely. The choice between global and row-wise sort depends on whether rows carry semantic meaning as units or are just a storage convenience.

Edge Cases and Rectangular Matrices

1×1 matrix

A 1×1 matrix has one element. Flatten produces a single-element array, sort is a no-op, refill writes it back unchanged. Output equals input. No special code branch is needed, though it is worth adding to a unit test to confirm the empty-matrix guard does not fire incorrectly.

Rectangular M×N matrices where M is not equal to N

The flatten-sort-refill algorithm does not assume a square matrix. A 2×4 matrix (8 elements) and a 4×2 matrix (also 8 elements) both flatten to the same 8-element 1D array. The only parameter that changes during refill is N (the column count):

# Rectangular example: 2 rows, 4 columns
matrix = [[4, 3, 1, 2],
          [8, 5, 7, 6]]
# Flatten: [4, 3, 1, 2, 8, 5, 7, 6]
# Sort:    [1, 2, 3, 4, 5, 6, 7, 8]
# Refill with n=4:
# Row 0: [1, 2, 3, 4]
# Row 1: [5, 6, 7, 8]

The same code works for any M and N as long as the refill loop uses the correct column count.

Empty matrix

If M equals 0 or N equals 0, the flatten step produces an empty array. Return early rather than proceed. The Python implementation shown above includes this guard at the top of the function.

In-Place vs Out-of-Place Tradeoff

Approach	Extra space	Code complexity	When to use
Out-of-place (separate 1D array)	O(M×N)	Low	Memory is not constrained; code clarity matters
In-place (virtual-index arithmetic)	O(1)	Medium	Memory is constrained; interview asks for constant extra space

The in-place approach avoids the intermediate array entirely. Access matrix[i][j] via a virtual index k = i×N + j, treating the 2D memory layout as a flat array. Any comparison sort that accepts a custom comparator can then sort by deriving the row and column from any given virtual index back to (k / N, k % N).

For a placement coding round under time pressure, the out-of-place version is cleaner to write and scores full marks. The in-place version becomes relevant when a follow-up question asks for O(1) extra space.

Complexity Summary

Operation	Time	Extra space
Flatten	O(M×N)	O(M×N) out-of-place
Sort	O(M×N log(M×N))	Depends on sort algorithm
Refill	O(M×N)	—
Total	O(M×N log(M×N))	O(M×N) out-of-place / O(1) in-place

The same nested-loop index arithmetic used here appears across 2D array problems. The Pascal’s triangle article shows how row-major construction applies to a triangular 2D array. For C-specific array and pointer questions that surface in aptitude tests, C coding questions set 1 covers the double-pointer and qsort comparator patterns that service-tier companies test most often.

The flatten-sort-refill pattern also appears in small ML preprocessing tasks: normalising a feature matrix, bucketing pixel intensity values, ranking activation scores. If testing that connection interests you, TinkerLLM at ₹299 provides a live environment where you can sort and reshape matrices in NumPy, feed the output into a classifier, and observe what changes when the sort order affects downstream predictions.