# Sort the given matrix

Given a n x n matrix. The problem is to sort the given matrix in strict order. Here strict order means that matrix is sorted in a way such that all elements in a row are sorted in increasing order and for row ‘i’, where 1 <= i <= n-1, first element of row 'i' is greater than or equal to the last element of row 'i-1'.

Examples:

```Input : mat[][] = { {5, 4, 7},
{1, 3, 8},
{2, 9, 6} }
Output : 1 2 3
4 5 6
7 8 9
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: Create a temp[] array of size n^2. Starting with the first row one by one copy the elements of the given matrix into temp[]. Sort temp[]. Now one by one copy the elements of temp[] back to the given matrix.

## C++

 `// C++ implementation to sort the given matrix ` `#include ` `using` `namespace` `std; ` ` `  `#define SIZE 10 ` ` `  `// function to sort the given matrix ` `void` `sortMat(``int` `mat[SIZE][SIZE], ``int` `n) ` `{ ` `    ``// temporary matrix of size n^2 ` `    ``int` `temp[n * n]; ` `    ``int` `k = 0; ` ` `  `    ``// copy the elements of matrix one by one ` `    ``// into temp[] ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``for` `(``int` `j = 0; j < n; j++) ` `            ``temp[k++] = mat[i][j]; ` ` `  `    ``// sort temp[] ` `    ``sort(temp, temp + k); ` `     `  `    ``// copy the elements of temp[] one by one ` `    ``// in mat[][] ` `    ``k = 0; ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``for` `(``int` `j = 0; j < n; j++) ` `            ``mat[i][j] = temp[k++]; ` `} ` ` `  `// function to print the given matrix ` `void` `printMat(``int` `mat[SIZE][SIZE], ``int` `n) ` `{ ` `    ``for` `(``int` `i = 0; i < n; i++) { ` `        ``for` `(``int` `j = 0; j < n; j++) ` `            ``cout << mat[i][j] << ``" "``; ` `        ``cout << endl; ` `    ``} ` `} ` ` `  `// Driver program to test above ` `int` `main() ` `{ ` `    ``int` `mat[SIZE][SIZE] = { { 5, 4, 7 }, ` `                            ``{ 1, 3, 8 }, ` `                            ``{ 2, 9, 6 } }; ` `    ``int` `n = 3; ` ` `  `    ``cout << ````"Original Matrix: "````; ` `    ``printMat(mat, n); ` ` `  `    ``sortMat(mat, n); ` ` `  `    ``cout << ````" Matrix After Sorting: "````; ` `    ``printMat(mat, n); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java implementation to  ` `// sort the given matrix ` `import` `java.io.*; ` `import` `java.util.*; ` ` `  `class` `GFG { ` `     `  `    ``static` `int` `SIZE = ``10``; ` ` `  `    ``// function to sort the given matrix ` `    ``static` `void` `sortMat(``int` `mat[][], ``int` `n) ` `    ``{ ` `        ``// temporary matrix of size n^2 ` `        ``int` `temp[] = ``new` `int``[n * n]; ` `        ``int` `k = ``0``; ` `     `  `        ``// copy the elements of matrix  ` `        ``// one by one into temp[] ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``for` `(``int` `j = ``0``; j < n; j++) ` `                ``temp[k++] = mat[i][j]; ` `     `  `        ``// sort temp[] ` `        ``Arrays.sort(temp); ` `         `  `        ``// copy the elements of temp[] ` `        ``// one by one in mat[][] ` `        ``k = ``0``; ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``for` `(``int` `j = ``0``; j < n; j++) ` `                ``mat[i][j] = temp[k++]; ` `    ``} ` `     `  `    ``// function to print the given matrix ` `    ``static` `void` `printMat(``int` `mat[][], ``int` `n) ` `    ``{ ` `        ``for` `(``int` `i = ``0``; i < n; i++) { ` `            ``for` `(``int` `j = ``0``; j < n; j++) ` `                ``System.out.print( mat[i][j] + ``" "``); ` `            ``System.out.println(); ` `        ``} ` `    ``} ` `     `  `    ``// Driver program to test above ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `mat[][] = { { ``5``, ``4``, ``7` `}, ` `                        ``{ ``1``, ``3``, ``8` `}, ` `                        ``{ ``2``, ``9``, ``6` `} }; ` `        ``int` `n = ``3``; ` `     `  `        ``System.out.println(``"Original Matrix:"``); ` `        ``printMat(mat, n); ` `     `  `        ``sortMat(mat, n); ` `     `  `        ``System.out.println(``"Matrix After Sorting:"``); ` `        ``printMat(mat, n); ` `     `  `    ``} ` `} ` ` `  `// This code is contributed by Nikita Tiwari. `

## Python3

 `# Python3 implementation to sort ` `# the given matrix ` ` `  `SIZE ``=` `10` ` `  `# Function to sort the given matrix ` `def` `sortMat(mat, n) : ` `     `  `    ``# Temporary matrix of size n^2 ` `    ``temp ``=` `[``0``] ``*` `(n ``*` `n) ` `    ``k ``=` `0` ` `  `    ``# Copy the elements of matrix   ` `    ``# one by one into temp[] ` `    ``for` `i ``in` `range``(``0``, n) : ` `         `  `        ``for` `j ``in` `range``(``0``, n) : ` `             `  `            ``temp[k] ``=` `mat[i][j] ` `            ``k ``+``=` `1` ` `  `    ``# sort temp[] ` `    ``temp.sort() ` `     `  `    ``# copy the elements of temp[]  ` `    ``# one by one in mat[][] ` `    ``k ``=` `0` `     `  `    ``for` `i ``in` `range``(``0``, n) : ` `         `  `        ``for` `j ``in` `range``(``0``, n) : ` `            ``mat[i][j] ``=` `temp[k] ` `            ``k ``+``=` `1` ` `  ` `  `# Function to print the given matrix ` `def` `printMat(mat, n) : ` `     `  `    ``for` `i ``in` `range``(``0``, n) : ` `         `  `        ``for` `j ``in` `range``( ``0``, n ) : ` `             `  `            ``print``(mat[i][j] , end ``=` `" "``) ` `             `  `        ``print``() ` `     `  `     `  `# Driver program to test above ` `mat ``=` `[ [ ``5``, ``4``, ``7` `], ` `        ``[ ``1``, ``3``, ``8` `], ` `        ``[ ``2``, ``9``, ``6` `] ] ` `n ``=` `3` ` `  `print``( ``"Original Matrix:"``) ` `printMat(mat, n) ` ` `  `sortMat(mat, n) ` ` `  `print``(````" Matrix After Sorting:"````) ` `printMat(mat, n) ` ` `  ` `  `# This code is contributed by Nikita Tiwari. `

## C#

 `// C# implementation to ` `// sort the given matrix ` `using` `System; ` ` `  `class` `GFG { ` `    ``static` `int` `SIZE = 10; ` ` `  `    ``// function to sort the given matrix ` `    ``static` `void` `sortMat(``int``[, ] mat, ``int` `n) ` `    ``{ ` `        ``// temporary matrix of size n^2 ` `        ``int``[] temp = ``new` `int``[n * n]; ` `        ``int` `k = 0; ` ` `  `        ``// copy the elements of matrix ` `        ``// one by one into temp[] ` `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``for` `(``int` `j = 0; j < n; j++) ` `                ``temp[k++] = mat[i, j]; ` ` `  `        ``// sort temp[] ` `        ``Array.Sort(temp); ` ` `  `        ``// copy the elements of temp[] ` `        ``// one by one in mat[][] ` `        ``k = 0; ` `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``for` `(``int` `j = 0; j < n; j++) ` `            ``mat[i, j] = temp[k++]; ` `    ``} ` ` `  `    ``// function to print the given matrix ` `    ``static` `void` `printMat(``int``[, ] mat, ``int` `n) ` `    ``{ ` `        ``for` `(``int` `i = 0; i < n; i++) { ` `            ``for` `(``int` `j = 0; j < n; j++) ` `            ``Console.Write(mat[i, j] + ``" "``); ` `            ``Console.WriteLine(); ` `        ``} ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int``[, ] mat = { { 5, 4, 7 }, ` `                        ``{ 1, 3, 8 }, ` `                        ``{ 2, 9, 6 } }; ` `        ``int` `n = 3; ` ` `  `        ``Console.WriteLine(``"Original Matrix:"``); ` `        ``printMat(mat, n); ` ` `  `        ``sortMat(mat, n); ` ` `  `        ``Console.WriteLine(``"Matrix After Sorting:"``); ` `        ``printMat(mat, n); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007 `

Output :

```Original Matrix:
5 4 7
1 3 8
2 9 6

Matrix After Sorting:
1 2 3
4 5 6
7 8 9
```

Time Complexity: O(n2log2n).
Auxiliary Space: O(n2).

## tags:

Matrix Sorting Sorting Matrix