Skip to main content

Convert given Matrix into sorted Spiral Matrix

The problem is to convert a given 2D matrix into a sorted spiral matrix. In a sorted spiral matrix, the elements are arranged in a spiral pattern starting from the top-left corner and moving in a clockwise direction.

Example

Consider the following 2D matrix:

4  6  2  2
3  7  6  5
1  5  6  6
5  5  4  8
1  5  12 9
7  5  2  3
1  9  8  10

The sorted spiral matrix will be:

1  1  1  2
6  6  6  2
6  12 7  2
5  10 7  3
5  9  8  3
5  9  8  4
5  5  5  4

Idea to Solve the Problem

To convert the given matrix into a sorted spiral matrix, we can perform the following steps:

  1. Collect all the elements of the matrix and store them in a 1D auxiliary array.
  2. Sort the auxiliary array in ascending order.
  3. Traverse the matrix in a spiral pattern from the top-left corner to the bottom-right corner and replace each element with the corresponding element from the sorted auxiliary array.

Algorithm

  1. Create a function print_matrix to display the elements of the matrix.
  2. Create a function merge_elements to merge two sorted subarrays of the auxiliary array.
  3. Create a function sort_element to perform a merge sort on the auxiliary array.
  4. Create a function update_element to update the matrix with elements from the sorted auxiliary array in a spiral pattern.
  5. Create a function sorted_spiral to convert the given matrix into a sorted spiral matrix.
  6. In the main function, define the 2D matrix and its dimensions.
  7. Display the original matrix.
  8. Call the sorted_spiral function to convert the matrix into a sorted spiral matrix.
  9. Display the sorted spiral matrix.

Pseudocode

sorted_spiral(row, col, matrix):
    size = row * col
    if size <= 0:
        return
    Create an auxiliary array 'auxiliary' of size 'size'
    k = 0
    for i from 0 to row-1:
        for j from 0 to col-1:
            auxiliary[k] = matrix[i][j]
            k = k + 1
    sort_element(auxiliary, 0, size - 1)
    update_element(row, col, matrix, auxiliary, 0, 0, row - 1, col - 1, size)

update_element(row, col, matrix, auxiliary, s_row, s_col, e_row, e_col, size):
    // Left to right
    for i from s_col to e_col and size > 0:
        matrix[s_row][i] = auxiliary[row * col - size]
        size = size - 1
    // Top to down
    for i from s_row + 1 to e_row and size > 0:
        matrix[i][e_col] = auxiliary[row * col - size]
        size = size - 1
    // Bottom right to bottom left
    for i from e_col - 1 to s_col and size > 0:
        matrix[e_row][i] = auxiliary[row * col - size]
        size = size - 1
    // Bottom left to top
    for i from e_row - 1 to s_row and size > 0:
        matrix[i][s_col] = auxiliary[row * col - size]
        size = size - 1
    if s_row + 1 <= e_row - 1 and size > 0:
        // Recursive call
        update_element(row, col, matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size)

// The remaining functions (print_matrix, merge_elements, sort_element) are also provided in the Java code.

Code Solution

// C Program
// Convert given Matrix into sorted Spiral Matrix
#include <stdio.h>

#define R 7
#define C 4
//Displaying of the matrix elements
void print_matrix(int matrix[R][C])
{
	int i;
	int j;
	for (i = 0; i < R; ++i)
	{
		for (j = 0; j < C; ++j)
		{
			printf("  %d", matrix[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}
//Sorted merge of given two subarrays of an array
void merge_elements(int auxiliary[], int front, int tail, int middle)
{
	//Get the size of first subarray
	int s1 = (middle - front) + 1;
	//Get the size of second subarray
	int s2 = tail - middle;
	//Creating auxiliary storage to store elements
	int first_subarray[s1];
	int second_subarray[s2];
	//Loop controlling variables
	int i = 0;
	int j = 0;
	int counter = 0;
	//Get the elements of first subarray
	for (i = 0; i < s1; i++)
	{
		first_subarray[i] = auxiliary[front + i];
	}
	//Get the elements of second subarray
	for (i = 0; i < s2; i++)
	{
		second_subarray[i] = auxiliary[middle + i + 1];
	}
	i = 0;
	// Add sorted elements into actual array
	while (counter < s1 + s2)
	{
		//Check that both sub array element exists or not
		if (i < s1 && j < s2)
		{
			if (first_subarray[i] <= second_subarray[j])
			{
				//When first array [i] element are smaller 
				auxiliary[front + counter] = first_subarray[i];
				i++;
			}
			else
			{
				//When second array [j] element are smaller 
				auxiliary[front + counter] = second_subarray[j];
				j++;
			}
		}
		else if (i < s1)
		{
			//When first sub array element exists
			auxiliary[front + counter] = first_subarray[i];
			i++;
		}
		else
		{
			//When second sub array element exists
			auxiliary[front + counter] = second_subarray[j];
			j++;
		}
		counter++;
	}
}
//Split the array elements into two parts
void sort_element(int auxiliary[], int front, int tail)
{
	if (front < tail)
	{
		//Get middle location of given index
		int middle = (front + tail) / 2;
		//Split the array into two parts
		sort_element(auxiliary, front, middle);
		sort_element(auxiliary, middle + 1, tail);
		//Combine split array into sorted way
		merge_elements(auxiliary, front, tail, middle);
	}
}
void update_element(int matrix[R][C], int auxiliary[], int s_row, int s_col, int e_row, int e_col, int size)
{
	//Left to right
	for (int i = s_col; i <= e_col && size > 0; ++i)
	{
		matrix[s_row][i] = auxiliary[R *C - size];
		size--;
	}
	//Top to down
	for (int i = s_row + 1; i <= e_row && size > 0; ++i)
	{
		matrix[i][e_col] = auxiliary[R *C - size];
		size--;
	}
	//Bottom right to bottom-left
	for (int i = e_col - 1; i >= s_col && size > 0; --i)
	{
		matrix[e_row][i] = auxiliary[R *C - size];
		size--;
	}
	//Bottom left to top
	for (int i = e_row - 1; i > s_row && size > 0; --i)
	{
		matrix[i][s_row] = auxiliary[R *C - size];
		size--;
	}
	if (s_row + 1 <= e_row - 1 && size > 0)
	{
		//Recursive call
		update_element(matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size);
	}
}
void sorted_spiral(int matrix[R][C])
{
	int size = R *C;
	if (size <= 0)
	{
		return;
	}
	int auxiliary[size];
	int i = 0;
	int j = 0;
	int k = 0;
	// Collect elements of 2d array
	for (i = 0; i < R; ++i)
	{
		for (j = 0; j < C; ++j)
		{
			auxiliary[k] = matrix[i][j];
			k++;
		}
	}
	sort_element(auxiliary, 0, size - 1);
	update_element(matrix, auxiliary, 0, 0, R - 1, C - 1, size);
}
int main()
{

    int matrix[R][C] =
    {
        {4, 6, 2 , 2 },
        {3, 7, 6 , 5 },
        {1, 5,  6,  6 },
        {5, 5,  4,  8 },
        {1, 5,  12,  9 },
        {7, 5,  2,  3 },
        {1, 9,  8,  10 }
    };
	printf("\n  Before sorted spiral\n");
	print_matrix(matrix);
	sorted_spiral(matrix);
	printf("\n  After sorted spiral\n");
	print_matrix(matrix);
	return 0;
}

Output

  Before sorted spiral
  4  6  2  2
  3  7  6  5
  1  5  6  6
  5  5  4  8
  1  5  12  9
  7  5  2  3
  1  9  8  10


  After sorted spiral
  1  1  1  2
  6  6  6  2
  6  12  7  2
  5  10  7  3
  5  9  8  3
  5  9  8  4
  5  5  5  4

/*
    Java program 
    Convert given Matrix into sorted Spiral Matrix
*/
// Define TreeNode
class MyMatrix
{
    //Displaying of the matrix elements
    public void print_matrix(int row, int col, int[][] matrix)
    {
        for (int i = 0; i < row; ++i)
        {
            for (int j = 0; j < col; ++j)
            {
                System.out.print("  " + matrix[i][j]  );
            }
            System.out.print("\n");
        }
        System.out.print("\n");
    }
    //Sorted merge of given two subarrays of an array
    public void merge_elements(int[] auxiliary, int front, int tail, int middle)
    {
        //Get the size of first subarray
        int s1 = (middle - front) + 1;
        //Get the size of second subarray
        int s2 = tail - middle;
        //Creating auxiliary storage to store elements
        int[] first_subarray = new int[s1];
        int[] second_subarray = new int[s2];
        //Loop controlling variables
        int i = 0;
        int j = 0;
        int counter = 0;
        //Get the elements of first subarray
        for (i = 0; i < s1; i++)
        {
            first_subarray[i] = auxiliary[front + i];
        }
        //Get the elements of second subarray
        for (i = 0; i < s2; i++)
        {
            second_subarray[i] = auxiliary[middle + i + 1];
        }
        i = 0;
        // Add sorted elements into actual array
        while (counter < s1 + s2)
        {
            //Check that both sub array element exists or not
            if (i < s1 && j < s2)
            {
                if (first_subarray[i] <= second_subarray[j])
                {
                    //When first array [i] element are smaller 
                    auxiliary[front + counter] = first_subarray[i];
                    i++;
                }
                else
                {
                    //When second array [j] element are smaller 
                    auxiliary[front + counter] = second_subarray[j];
                    j++;
                }
            }
            else if (i < s1)
            {
                //When first sub array element exists
                auxiliary[front + counter] = first_subarray[i];
                i++;
            }
            else
            {
                //When second sub array element exists
                auxiliary[front + counter] = second_subarray[j];
                j++;
            }
            counter++;
        }
    }
    //Split the array elements into two parts
    public void sort_element(int[] auxiliary, int front, int tail)
    {
        if (front < tail)
        {
            //Get middle location of given index
            int middle = (front + tail) / 2;
            //Split the array into two parts
            sort_element(auxiliary, front, middle);
            sort_element(auxiliary, middle + 1, tail);
            //Combine split array into sorted way
            merge_elements(auxiliary, front, tail, middle);
        }
    }
    public void update_element(int row, int col, int[][] matrix, int[] auxiliary, int s_row, int s_col, int e_row, int e_col, int size)
    {
        //Left to right
        for (int i = s_col; i <= e_col && size > 0; ++i)
        {
            matrix[s_row][i] = auxiliary[row * col - size];
            size--;
        }
        //Top to down
        for (int i = s_row + 1; i <= e_row && size > 0; ++i)
        {
            matrix[i][e_col] = auxiliary[row * col - size];
            size--;
        }
        //Bottom right to bottom-left
        for (int i = e_col - 1; i >= s_col && size > 0; --i)
        {
            matrix[e_row][i] = auxiliary[row * col - size];
            size--;
        }
        //Bottom left to top
        for (int i = e_row - 1; i > s_row && size > 0; --i)
        {
            matrix[i][s_row] = auxiliary[row * col - size];
            size--;
        }
        if (s_row + 1 <= e_row - 1 && size > 0)
        {
            //Recursive call
            update_element(row, col, matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size);
        }
    }
    public void sorted_spiral(int row, int col, int[][] matrix)
    {
        int size = row * col;
        if (size <= 0)
        {
            return;
        }
        int[] auxiliary = new int[size];
        int i = 0;
        int j = 0;
        int k = 0;
        // Collect elements of 2d array
        for (i = 0; i < row; ++i)
        {
            for (j = 0; j < col; ++j)
            {
                auxiliary[k] = matrix[i][j];
                k++;
            }
        }
        sort_element(auxiliary, 0, size - 1);
        update_element(row, col, matrix, auxiliary, 0, 0, row - 1, col - 1, size);
    }
    public static void main(String[] args)
    {
        MyMatrix obj = new MyMatrix();
        // Define matrix of integer elements
        int[][] matrix ={
            {4, 6, 2 , 2 },
            {3, 7, 6 , 5 },
            {1, 5,  6,  6 },
            {5, 5,  4,  8 },
            {1, 5,  12,  9 },
            {7, 5,  2,  3 },
            {1, 9,  8,  10 }
        };

        int row = matrix.length;
        int col = matrix[0].length;
        System.out.print("\n Before sorted spiral\n");
        obj.print_matrix(row, col, matrix);
        obj.sorted_spiral(row, col, matrix);
        System.out.print("\n After sorted spiral\n");
        obj.print_matrix(row, col, matrix);
    
        
    }
}

Output

 Before sorted spiral
  4  6  2  2
  3  7  6  5
  1  5  6  6
  5  5  4  8
  1  5  12  9
  7  5  2  3
  1  9  8  10


 After sorted spiral
  1  1  1  2
  6  6  6  2
  6  12  7  2
  5  10  7  3
  5  9  8  3
  5  9  8  4
  5  5  5  4

// Include header file
#include <iostream>
#define R 7
#define C 4
using namespace std;
/*
    C++ program 
    Convert given Matrix into sorted Spiral Matrix
*/
//  Define TreeNode
class MyMatrix
{
	public:
		// Displaying of the matrix elements
		void print_matrix(int matrix[R][C] )
		{
			for (int i = 0; i < R; ++i)
			{
				for (int j = 0; j < C; ++j)
				{
					cout << "  " << matrix[i][j];
				}
				cout << "\n";
			}
			cout << "\n";
		}
	// Sorted merge of given two subarrays of an array
	void merge_elements(int auxiliary[], int front, int tail, int middle)
	{
		// Get the size of first subarray
		int s1 = (middle - front) + 1;
		// Get the size of second subarray
		int s2 = tail - middle;
		// Creating auxiliary storage to store elements
		int first_subarray[s1];
		int second_subarray[s2];
		// Loop controlling variables
		int i = 0;
		int j = 0;
		int counter = 0;
		// Get the elements of first subarray
		for (i = 0; i < s1; i++)
		{
			first_subarray[i] = auxiliary[front + i];
		}
		// Get the elements of second subarray
		for (i = 0; i < s2; i++)
		{
			second_subarray[i] = auxiliary[middle + i + 1];
		}
		i = 0;
		//  Add sorted elements into actual array
		while (counter < s1 + s2)
		{
			// Check that both sub array element exists or not
			if (i < s1 && j < s2)
			{
				if (first_subarray[i] <= second_subarray[j])
				{
					// When first array [i] element are smaller
					auxiliary[front + counter] = first_subarray[i];
					i++;
				}
				else
				{
					// When second array [j] element are smaller
					auxiliary[front + counter] = second_subarray[j];
					j++;
				}
			}
			else if (i < s1)
			{
				// When first sub array element exists
				auxiliary[front + counter] = first_subarray[i];
				i++;
			}
			else
			{
				// When second sub array element exists
				auxiliary[front + counter] = second_subarray[j];
				j++;
			}
			counter++;
		}
	}
	// Split the array elements into two parts
	void sort_element(int auxiliary[], int front, int tail)
	{
		if (front < tail)
		{
			// Get middle location of given index
			int middle = (front + tail) / 2;
			// Split the array into two parts
			this->sort_element(auxiliary, front, middle);
			this->sort_element(auxiliary, middle + 1, tail);
			// Combine split array into sorted way
			this->merge_elements(auxiliary, front, tail, middle);
		}
	}
	void update_element(int matrix[R][C], int auxiliary[], int s_row, int s_col, int e_row, int e_col, int size)
	{
		// Left to right
		for (int i = s_col; i <= e_col && size > 0; ++i)
		{
			matrix[s_row][i] = auxiliary[R * C  - size];
			size--;
		}
		// Top to down
		for (int i = s_row + 1; i <= e_row && size > 0; ++i)
		{
			matrix[i][e_col] = auxiliary[R * C - size];
			size--;
		}
		// Bottom right to bottom-left
		for (int i = e_col - 1; i >= s_col && size > 0; --i)
		{
			matrix[e_row][i] = auxiliary[R * C - size];
			size--;
		}
		// Bottom left to top
		for (int i = e_row - 1; i > s_row && size > 0; --i)
		{
			matrix[i][s_row] = auxiliary[R * C - size];
			size--;
		}
		if (s_row + 1 <= e_row - 1 && size > 0)
		{
			// Recursive call
			this->update_element( matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size);
		}
	}
	void sorted_spiral(int matrix[R][C])
	{
		int size = R * C;
		if (size <= 0)
		{
			return;
		}
		int auxiliary[size];
		int i = 0;
		int j = 0;
		int k = 0;
		//  Collect elements of 2d array
		for (i = 0; i < R; ++i)
		{
			for (j = 0; j < C; ++j)
			{
				auxiliary[k] = matrix[i][j];
				k++;
			}
		}
		this->sort_element(auxiliary, 0, size - 1);
		this->update_element( matrix, auxiliary, 0, 0, R - 1, C - 1, size);
	}
};
int main()
{
	MyMatrix obj = MyMatrix();
	//  Define matrix of integer elements
	int matrix[R][C] =     
    {
        {4, 6, 2 , 2 },
        {3, 7, 6 , 5 },
        {1, 5,  6,  6 },
        {5, 5,  4,  8 },
        {1, 5,  12,  9 },
        {7, 5,  2,  3 },
        {1, 9,  8,  10 }
    };
	
	cout << "\n Before sorted spiral\n";
	obj.print_matrix(matrix);
	obj.sorted_spiral(matrix);
	cout << "\n After sorted spiral\n";
	obj.print_matrix(matrix);
	return 0;
}

Output

 Before sorted spiral
  4  6  2  2
  3  7  6  5
  1  5  6  6
  5  5  4  8
  1  5  12  9
  7  5  2  3
  1  9  8  10


 After sorted spiral
  1  1  1  2
  6  6  6  2
  6  12  7  2
  5  10  7  3
  5  9  8  3
  5  9  8  4
  5  5  5  4

// Include namespace system
using System;
/*
    C# program 
    Convert given Matrix into sorted Spiral Matrix
*/
//  Define TreeNode
public class MyMatrix
{
	// Displaying of the matrix elements
	public void print_matrix(int row, int col, int[,] matrix)
	{
		for (int i = 0; i < row; ++i)
		{
			for (int j = 0; j < col; ++j)
			{
				Console.Write("  " + matrix[i,j]);
			}
			Console.Write("\n");
		}
		Console.Write("\n");
	}
	// Sorted merge of given two subarrays of an array
	public void merge_elements(int[] auxiliary, int front, int tail, int middle)
	{
		// Get the size of first subarray
		int s1 = (middle - front) + 1;
		// Get the size of second subarray
		int s2 = tail - middle;
		// Creating auxiliary storage to store elements
		int[] first_subarray = new int[s1];
		int[] second_subarray = new int[s2];
		// Loop controlling variables
		int i = 0;
		int j = 0;
		int counter = 0;
		// Get the elements of first subarray
		for (i = 0; i < s1; i++)
		{
			first_subarray[i] = auxiliary[front + i];
		}
		// Get the elements of second subarray
		for (i = 0; i < s2; i++)
		{
			second_subarray[i] = auxiliary[middle + i + 1];
		}
		i = 0;
		//  Add sorted elements into actual array
		while (counter < s1 + s2)
		{
			// Check that both sub array element exists or not
			if (i < s1 && j < s2)
			{
				if (first_subarray[i] <= second_subarray[j])
				{
					// When first array [i] element are smaller
					auxiliary[front + counter] = first_subarray[i];
					i++;
				}
				else
				{
					// When second array [j] element are smaller
					auxiliary[front + counter] = second_subarray[j];
					j++;
				}
			}
			else if (i < s1)
			{
				// When first sub array element exists
				auxiliary[front + counter] = first_subarray[i];
				i++;
			}
			else
			{
				// When second sub array element exists
				auxiliary[front + counter] = second_subarray[j];
				j++;
			}
			counter++;
		}
	}
	// Split the array elements into two parts
	public void sort_element(int[] auxiliary, int front, int tail)
	{
		if (front < tail)
		{
			// Get middle location of given index
			int middle = (front + tail) / 2;
			// Split the array into two parts
			sort_element(auxiliary, front, middle);
			sort_element(auxiliary, middle + 1, tail);
			// Combine split array into sorted way
			merge_elements(auxiliary, front, tail, middle);
		}
	}
	public void update_element(int row, int col, int[,] matrix, int[] auxiliary, int s_row, int s_col, int e_row, int e_col, int size)
	{
		// Left to right
		for (int i = s_col; i <= e_col && size > 0; ++i)
		{
			matrix[s_row,i] = auxiliary[row * col - size];
			size--;
		}
		// Top to down
		for (int i = s_row + 1; i <= e_row && size > 0; ++i)
		{
			matrix[i,e_col] = auxiliary[row * col - size];
			size--;
		}
		// Bottom right to bottom-left
		for (int i = e_col - 1; i >= s_col && size > 0; --i)
		{
			matrix[e_row,i] = auxiliary[row * col - size];
			size--;
		}
		// Bottom left to top
		for (int i = e_row - 1; i > s_row && size > 0; --i)
		{
			matrix[i,s_row] = auxiliary[row * col - size];
			size--;
		}
		if (s_row + 1 <= e_row - 1 && size > 0)
		{
			// Recursive call
			update_element(row, col, matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size);
		}
	}
	public void sorted_spiral(int row, int col, int[,] matrix)
	{
		int size = row * col;
		if (size <= 0)
		{
			return;
		}
		int[] auxiliary = new int[size];
		int i = 0;
		int j = 0;
		int k = 0;
		//  Collect elements of 2d array
		for (i = 0; i < row; ++i)
		{
			for (j = 0; j < col; ++j)
			{
				auxiliary[k] = matrix[i,j];
				k++;
			}
		}
		sort_element(auxiliary, 0, size - 1);
		update_element(row, col, matrix, auxiliary, 0, 0, row - 1, col - 1, size);
	}
	public static void Main(String[] args)
	{
		MyMatrix obj = new MyMatrix();
		//  Define matrix of integer elements
		int[,] matrix =    {
            {4, 6, 2 , 2 },
            {3, 7, 6 , 5 },
            {1, 5,  6,  6 },
            {5, 5,  4,  8 },
            {1, 5,  12,  9 },
            {7, 5,  2,  3 },
            {1, 9,  8,  10 }
        };
		int row = matrix.GetLength(0);
		int col = matrix.GetLength(1);
		Console.Write("\n Before sorted spiral\n");
		obj.print_matrix(row, col, matrix);
		obj.sorted_spiral(row, col, matrix);
		Console.Write("\n After sorted spiral\n");
		obj.print_matrix(row, col, matrix);
	}
}

Output

 Before sorted spiral
  4  6  2  2
  3  7  6  5
  1  5  6  6
  5  5  4  8
  1  5  12  9
  7  5  2  3
  1  9  8  10


 After sorted spiral
  1  1  1  2
  6  6  6  2
  6  12  7  2
  5  10  7  3
  5  9  8  3
  5  9  8  4
  5  5  5  4

<?php
/*
    Php program 
    Convert given Matrix into sorted Spiral Matrix
*/
//  Define TreeNode
class MyMatrix
{
	// Displaying of the matrix elements
	public	function print_matrix($row, $col, & $matrix)
	{
		for ($i = 0; $i < $row; ++$i)
		{
			for ($j = 0; $j < $col; ++$j)
			{
				echo "  ". $matrix[$i][$j];
			}
			echo "\n";
		}
		echo "\n";
	}
	// Sorted merge of given two subarrays of an array
	public	function merge_elements( & $auxiliary, $front, $tail, $middle)
	{
		// Get the size of first subarray
		$s1 = ($middle - $front) + 1;
		// Get the size of second subarray
		$s2 = $tail - $middle;
		// Creating auxiliary storage to store elements
		$first_subarray = array_fill(0, $s1, 0);
		$second_subarray = array_fill(0, $s2, 0);
		// Loop controlling variables
		$i = 0;
		$j = 0;
		$counter = 0;
		// Get the elements of first subarray
		for ($i = 0; $i < $s1; $i++)
		{
			$first_subarray[$i] = $auxiliary[$front + $i];
		}
		// Get the elements of second subarray
		for ($i = 0; $i < $s2; $i++)
		{
			$second_subarray[$i] = $auxiliary[$middle + $i + 1];
		}
		$i = 0;
		//  Add sorted elements into actual array
		while ($counter < $s1 + $s2)
		{
			// Check that both sub array element exists or not
			if ($i < $s1 && $j < $s2)
			{
				if ($first_subarray[$i] <= $second_subarray[$j])
				{
					// When first array [i] element are smaller
					$auxiliary[$front + $counter] = $first_subarray[$i];
					$i++;
				}
				else
				{
					// When second array [j] element are smaller
					$auxiliary[$front + $counter] = $second_subarray[$j];
					$j++;
				}
			}
			else if ($i < $s1)
			{
				// When first sub array element exists
				$auxiliary[$front + $counter] = $first_subarray[$i];
				$i++;
			}
			else
			{
				// When second sub array element exists
				$auxiliary[$front + $counter] = $second_subarray[$j];
				$j++;
			}
			$counter++;
		}
	}
	// Split the array elements into two parts
	public	function sort_element( & $auxiliary, $front, $tail)
	{
		if ($front < $tail)
		{
			// Get middle location of given index
			$middle = intval(($front + $tail) / 2);
			// Split the array into two parts
			$this->sort_element($auxiliary, $front, $middle);
			$this->sort_element($auxiliary, $middle + 1, $tail);
			// Combine split array into sorted way
			$this->merge_elements($auxiliary, $front, $tail, $middle);
		}
	}
	public	function update_element($row, $col, & $matrix, & $auxiliary, $s_row, $s_col, $e_row, $e_col, $size)
	{
		// Left to right
		for ($i = $s_col; $i <= $e_col && $size > 0; ++$i)
		{
			$matrix[$s_row][$i] = $auxiliary[$row * $col - $size];
			$size--;
		}
		// Top to down
		for ($i = $s_row + 1; $i <= $e_row && $size > 0; ++$i)
		{
			$matrix[$i][$e_col] = $auxiliary[$row * $col - $size];
			$size--;
		}
		// Bottom right to bottom-left
		for ($i = $e_col - 1; $i >= $s_col && $size > 0; --$i)
		{
			$matrix[$e_row][$i] = $auxiliary[$row * $col - $size];
			$size--;
		}
		// Bottom left to top
		for ($i = $e_row - 1; $i > $s_row && $size > 0; --$i)
		{
			$matrix[$i][$s_row] = $auxiliary[$row * $col - $size];
			$size--;
		}
		if ($s_row + 1 <= $e_row - 1 && $size > 0)
		{
			// Recursive call
			$this->update_element($row, $col, $matrix, $auxiliary, $s_row + 1, $s_col + 1, $e_row - 1, $e_col - 1, $size);
		}
	}
	public	function sorted_spiral($row, $col, & $matrix)
	{
		$size = $row * $col;
		if ($size <= 0)
		{
			return;
		}
		$auxiliary = array_fill(0, $size, 0);
		$i = 0;
		$j = 0;
		$k = 0;
		//  Collect elements of 2d array
		for ($i = 0; $i < $row; ++$i)
		{
			for ($j = 0; $j < $col; ++$j)
			{
				$auxiliary[$k] = $matrix[$i][$j];
				$k++;
			}
		}
		$this->sort_element($auxiliary, 0, $size - 1);
		$this->update_element($row, $col, $matrix, $auxiliary, 0, 0, $row - 1, $col - 1, $size);
	}
}

function main()
{
	$obj = new MyMatrix();
	//  Define matrix of integer elements
	$matrix = array(
      array(4, 6, 2, 2), 
      array(3, 7, 6, 5), 
      array(1, 5, 6, 6), 
      array(5, 5, 4, 8), 
      array(1, 5, 12, 9), 
      array(7, 5, 2, 3), 
      array(1, 9, 8, 10));
	$row = count($matrix);
	$col = count($matrix[0]);
	echo "\n Before sorted spiral\n";
	$obj->print_matrix($row, $col, $matrix);
	$obj->sorted_spiral($row, $col, $matrix);
	echo "\n After sorted spiral\n";
	$obj->print_matrix($row, $col, $matrix);
}
main();

Output

 Before sorted spiral
  4  6  2  2
  3  7  6  5
  1  5  6  6
  5  5  4  8
  1  5  12  9
  7  5  2  3
  1  9  8  10


 After sorted spiral
  1  1  1  2
  6  6  6  2
  6  12  7  2
  5  10  7  3
  5  9  8  3
  5  9  8  4
  5  5  5  4

/*
    Node Js program 
    Convert given Matrix into sorted Spiral Matrix
*/
//  Define TreeNode
class MyMatrix
{
	// Displaying of the matrix elements
	print_matrix(row, col, matrix)
	{
		for (var i = 0; i < row; ++i)
		{
			for (var j = 0; j < col; ++j)
			{
				process.stdout.write("  " + matrix[i][j]);
			}
			process.stdout.write("\n");
		}
		process.stdout.write("\n");
	}
	// Sorted merge of given two subarrays of an array
	merge_elements(auxiliary, front, tail, middle)
	{
		// Get the size of first subarray
		var s1 = (middle - front) + 1;
		// Get the size of second subarray
		var s2 = tail - middle;
		// Creating auxiliary storage to store elements
		var first_subarray = Array(s1).fill(0);
		var second_subarray = Array(s2).fill(0);
		// Loop controlling variables
		var i = 0;
		var j = 0;
		var counter = 0;
		// Get the elements of first subarray
		for (i = 0; i < s1; i++)
		{
			first_subarray[i] = auxiliary[front + i];
		}
		// Get the elements of second subarray
		for (i = 0; i < s2; i++)
		{
			second_subarray[i] = auxiliary[middle + i + 1];
		}
		i = 0;
		//  Add sorted elements into actual array
		while (counter < s1 + s2)
		{
			// Check that both sub array element exists or not
			if (i < s1 && j < s2)
			{
				if (first_subarray[i] <= second_subarray[j])
				{
					// When first array [i] element are smaller
					auxiliary[front + counter] = first_subarray[i];
					i++;
				}
				else
				{
					// When second array [j] element are smaller
					auxiliary[front + counter] = second_subarray[j];
					j++;
				}
			}
			else if (i < s1)
			{
				// When first sub array element exists
				auxiliary[front + counter] = first_subarray[i];
				i++;
			}
			else
			{
				// When second sub array element exists
				auxiliary[front + counter] = second_subarray[j];
				j++;
			}
			counter++;
		}
	}
	// Split the array elements into two parts
	sort_element(auxiliary, front, tail)
	{
		if (front < tail)
		{
			// Get middle location of given index
			var middle = parseInt((front + tail) / 2);
			// Split the array into two parts
			this.sort_element(auxiliary, front, middle);
			this.sort_element(auxiliary, middle + 1, tail);
			// Combine split array into sorted way
			this.merge_elements(auxiliary, front, tail, middle);
		}
	}
	update_element(row, col, matrix, auxiliary, s_row, s_col, e_row, e_col, size)
	{
		// Left to right
		for (var i = s_col; i <= e_col && size > 0; ++i)
		{
			matrix[s_row][i] = auxiliary[row * col - size];
			size--;
		}
		// Top to down
		for (var i = s_row + 1; i <= e_row && size > 0; ++i)
		{
			matrix[i][e_col] = auxiliary[row * col - size];
			size--;
		}
		// Bottom right to bottom-left
		for (var i = e_col - 1; i >= s_col && size > 0; --i)
		{
			matrix[e_row][i] = auxiliary[row * col - size];
			size--;
		}
		// Bottom left to top
		for (var i = e_row - 1; i > s_row && size > 0; --i)
		{
			matrix[i][s_row] = auxiliary[row * col - size];
			size--;
		}
		if (s_row + 1 <= e_row - 1 && size > 0)
		{
			// Recursive call
			this.update_element(row, col, matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size);
		}
	}
	sorted_spiral(row, col, matrix)
	{
		var size = row * col;
		if (size <= 0)
		{
			return;
		}
		var auxiliary = Array(size).fill(0);
		var i = 0;
		var j = 0;
		var k = 0;
		//  Collect elements of 2d array
		for (i = 0; i < row; ++i)
		{
			for (j = 0; j < col; ++j)
			{
				auxiliary[k] = matrix[i][j];
				k++;
			}
		}
		this.sort_element(auxiliary, 0, size - 1);
		this.update_element(row, col, matrix, auxiliary, 0, 0, row - 1, col - 1, size);
	}
}

function main()
{
	var obj = new MyMatrix();
	//  Define matrix of integer elements
	var matrix = [
		[4, 6, 2, 2] , 
      	[3, 7, 6, 5] , 
      	[1, 5, 6, 6] , 
      	[5, 5, 4, 8] , 
      	[1, 5, 12, 9] , 
      	[7, 5, 2, 3] , 
      	[1, 9, 8, 10]
	];
	var row = matrix.length;
	var col = matrix[0].length;
	process.stdout.write("\n Before sorted spiral\n");
	obj.print_matrix(row, col, matrix);
	obj.sorted_spiral(row, col, matrix);
	process.stdout.write("\n After sorted spiral\n");
	obj.print_matrix(row, col, matrix);
}
main();

Output

 Before sorted spiral
  4  6  2  2
  3  7  6  5
  1  5  6  6
  5  5  4  8
  1  5  12  9
  7  5  2  3
  1  9  8  10


 After sorted spiral
  1  1  1  2
  6  6  6  2
  6  12  7  2
  5  10  7  3
  5  9  8  3
  5  9  8  4
  5  5  5  4

#  Python 3 program 
#  Convert given Matrix into sorted Spiral Matrix

#   Define TreeNode
class MyMatrix :
	#  Displaying of the matrix elements
	def print_matrix(self, row, col, matrix) :
		i = 0
		while (i < row) :
			j = 0
			while (j < col) :
				print("  ", matrix[i][j], end = "")
				j += 1
			
			print("\n", end = "")
			i += 1
		
		print("\n", end = "")
	
	#  Sorted merge of given two subarrays of an array
	def merge_elements(self, auxiliary, front, tail, middle) :
		#  Get the size of first subarray
		s1 = (middle - front) + 1
		#  Get the size of second subarray
		s2 = tail - middle
		#  Creating auxiliary storage to store elements
		first_subarray = [0] * (s1)
		second_subarray = [0] * (s2)
		#  Loop controlling variables
		i = 0
		j = 0
		counter = 0
		#  Get the elements of first subarray
		while (i < s1) :
			first_subarray[i] = auxiliary[front + i]
			i += 1
		
		#  Get the elements of second subarray
		i = 0
		while (i < s2) :
			second_subarray[i] = auxiliary[middle + i + 1]
			i += 1
		
		i = 0
		#   Add sorted elements into actual array
		while (counter < s1 + s2) :
			#  Check that both sub array element exists or not
			if (i < s1 and j < s2) :
				if (first_subarray[i] <= second_subarray[j]) :
					#  When first array [i] element are smaller
					auxiliary[front + counter] = first_subarray[i]
					i += 1
				else :
					#  When second array [j] element are smaller
					auxiliary[front + counter] = second_subarray[j]
					j += 1
				
			
			elif(i < s1) :
				#  When first sub array element exists
				auxiliary[front + counter] = first_subarray[i]
				i += 1
			else :
				#  When second sub array element exists
				auxiliary[front + counter] = second_subarray[j]
				j += 1
			
			counter += 1
		
	
	#  Split the array elements into two parts
	def sort_element(self, auxiliary, front, tail) :
		if (front < tail) :
			#  Get middle location of given index
			middle = int((front + tail) / 2)
			#  Split the array into two parts
			self.sort_element(auxiliary, front, middle)
			self.sort_element(auxiliary, middle + 1, tail)
			#  Combine split array into sorted way
			self.merge_elements(auxiliary, front, tail, middle)
		
	
	def update_element(self, row, col, matrix, auxiliary, s_row, s_col, e_row, e_col, size) :
		#  Left to right
		i = s_col
		while (i <= e_col and size > 0) :
			matrix[s_row][i] = auxiliary[row * col - size]
			size -= 1
			i += 1
		
		#  Top to down
		i = s_row + 1
		while (i <= e_row and size > 0) :
			matrix[i][e_col] = auxiliary[row * col - size]
			size -= 1
			i += 1
		
		#  Bottom right to bottom-left
		i = e_col - 1
		while (i >= s_col and size > 0) :
			matrix[e_row][i] = auxiliary[row * col - size]
			size -= 1
			i -= 1
		
		#  Bottom left to top
		i = e_row - 1
		while (i > s_row and size > 0) :
			matrix[i][s_row] = auxiliary[row * col - size]
			size -= 1
			i -= 1
		
		if (s_row + 1 <= e_row - 1 and size > 0) :
			#  Recursive call
			self.update_element(row, col, matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size)
		
	
	def sorted_spiral(self, row, col, matrix) :
		size = row * col
		if (size <= 0) :
			return
		
		auxiliary = [0] * (size)
		i = 0
		j = 0
		k = 0
		#   Collect elements of 2d array
		while (i < row) :
			j = 0
			while (j < col) :
				auxiliary[k] = matrix[i][j]
				k += 1
				j += 1
			
			i += 1
		
		self.sort_element(auxiliary, 0, size - 1)
		self.update_element(row, col, matrix, auxiliary, 0, 0, row - 1, col - 1, size)
	

def main() :
	obj = MyMatrix()
	#   Define matrix of integer elements
	matrix = [
		[4, 6, 2, 2] , 
      	[3, 7, 6, 5] , 
      	[1, 5, 6, 6] , 
      	[5, 5, 4, 8] , 
      	[1, 5, 12, 9] , 
      	[7, 5, 2, 3] , 
      	[1, 9, 8, 10]
	]
	row = len(matrix)
	col = len(matrix[0])
	print("\n Before sorted spiral\n", end = "")
	obj.print_matrix(row, col, matrix)
	obj.sorted_spiral(row, col, matrix)
	print("\n After sorted spiral\n", end = "")
	obj.print_matrix(row, col, matrix)

if __name__ == "__main__": main()

Output

 Before sorted spiral
   4   6   2   2
   3   7   6   5
   1   5   6   6
   5   5   4   8
   1   5   12   9
   7   5   2   3
   1   9   8   10


 After sorted spiral
   1   1   1   2
   6   6   6   2
   6   12   7   2
   5   10   7   3
   5   9   8   3
   5   9   8   4
   5   5   5   4

#  Ruby program 
#  Convert given Matrix into sorted Spiral Matrix

#   Define TreeNode
class MyMatrix 
	#  Displaying of the matrix elements
	def print_matrix(row, col, matrix) 
		i = 0
		while (i < row) 
			j = 0
			while (j < col) 
				print("  ", matrix[i][j])
				j += 1
			end

			print("\n")
			i += 1
		end

		print("\n")
	end

	#  Sorted merge of given two subarrays of an array
	def merge_elements(auxiliary, front, tail, middle) 
		#  Get the size of first subarray
		s1 = (middle - front) + 1
		#  Get the size of second subarray
		s2 = tail - middle
		#  Creating auxiliary storage to store elements
		first_subarray = Array.new(s1) {0}
		second_subarray = Array.new(s2) {0}
		#  Loop controlling variables
		i = 0
		j = 0
		counter = 0
		#  Get the elements of first subarray
		while (i < s1) 
			first_subarray[i] = auxiliary[front + i]
			i += 1
		end

		#  Get the elements of second subarray
		i = 0
		while (i < s2) 
			second_subarray[i] = auxiliary[middle + i + 1]
			i += 1
		end

		i = 0
		#   Add sorted elements into actual array
		while (counter < s1 + s2) 
			#  Check that both sub array element exists or not
			if (i < s1 && j < s2) 
				if (first_subarray[i] <= second_subarray[j]) 
					#  When first array [i] element are smaller
					auxiliary[front + counter] = first_subarray[i]
					i += 1
				else 
					#  When second array [j] element are smaller
					auxiliary[front + counter] = second_subarray[j]
					j += 1
				end

			elsif(i < s1) 
				#  When first sub array element exists
				auxiliary[front + counter] = first_subarray[i]
				i += 1
			else 
				#  When second sub array element exists
				auxiliary[front + counter] = second_subarray[j]
				j += 1
			end

			counter += 1
		end

	end

	#  Split the array elements into two parts
	def sort_element(auxiliary, front, tail) 
		if (front < tail) 
			#  Get middle location of given index
			middle = (front + tail) / 2
			#  Split the array into two parts
			self.sort_element(auxiliary, front, middle)
			self.sort_element(auxiliary, middle + 1, tail)
			#  Combine split array into sorted way
			self.merge_elements(auxiliary, front, tail, middle)
		end

	end

	def update_element(row, col, matrix, auxiliary, s_row, s_col, e_row, e_col, size) 
		#  Left to right
		i = s_col
		while (i <= e_col && size > 0) 
			matrix[s_row][i] = auxiliary[row * col - size]
			size -= 1
			i += 1
		end

		#  Top to down
		i = s_row + 1
		while (i <= e_row && size > 0) 
			matrix[i][e_col] = auxiliary[row * col - size]
			size -= 1
			i += 1
		end

		#  Bottom right to bottom-left
		i = e_col - 1
		while (i >= s_col && size > 0) 
			matrix[e_row][i] = auxiliary[row * col - size]
			size -= 1
			i -= 1
		end

		#  Bottom left to top
		i = e_row - 1
		while (i > s_row && size > 0) 
			matrix[i][s_row] = auxiliary[row * col - size]
			size -= 1
			i -= 1
		end

		if (s_row + 1 <= e_row - 1 && size > 0) 
			#  Recursive call
			self.update_element(row, col, matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size)
		end

	end

	def sorted_spiral(row, col, matrix) 
		size = row * col
		if (size <= 0) 
			return
		end

		auxiliary = Array.new(size) {0}
		i = 0
		j = 0
		k = 0
		#   Collect elements of 2d array
		while (i < row) 
			j = 0
			while (j < col) 
				auxiliary[k] = matrix[i][j]
				k += 1
				j += 1
			end

			i += 1
		end

		self.sort_element(auxiliary, 0, size - 1)
		self.update_element(row, col, matrix, auxiliary, 0, 0, row - 1, col - 1, size)
	end

end

def main() 
	obj = MyMatrix.new()
	#   Define matrix of integer elements
	matrix = [
		[4, 6, 2, 2] , 
        [3, 7, 6, 5] , 
        [1, 5, 6, 6] , 
        [5, 5, 4, 8] , 
        [1, 5, 12, 9] , 
        [7, 5, 2, 3] , 
        [1, 9, 8, 10]
	]
	row = matrix.length
	col = matrix[0].length
	print("\n Before sorted spiral\n")
	obj.print_matrix(row, col, matrix)
	obj.sorted_spiral(row, col, matrix)
	print("\n After sorted spiral\n")
	obj.print_matrix(row, col, matrix)
end

main()

Output

 Before sorted spiral
  4  6  2  2
  3  7  6  5
  1  5  6  6
  5  5  4  8
  1  5  12  9
  7  5  2  3
  1  9  8  10


 After sorted spiral
  1  1  1  2
  6  6  6  2
  6  12  7  2
  5  10  7  3
  5  9  8  3
  5  9  8  4
  5  5  5  4


/*
    Scala program 
    Convert given Matrix into sorted Spiral Matrix
*/
//   Define TreeNode
class MyMatrix
{
	//  Displaying of the matrix elements
	def print_matrix(row: Int, col: Int, matrix: Array[Array[Int]]): Unit = {
		var i: Int = 0;
		while (i < row)
		{
			var j: Int = 0;
			while (j < col)
			{
				print("  " + matrix(i)(j));
				j += 1;
			}
			print("\n");
			i += 1;
		}
		print("\n");
	}
	//  Sorted merge of given two subarrays of an array
	def merge_elements(auxiliary: Array[Int], front: Int, tail: Int, middle: Int): Unit = {
		//  Get the size of first subarray
		var s1: Int = (middle - front) + 1;
		//  Get the size of second subarray
		var s2: Int = tail - middle;
		//  Creating auxiliary storage to store elements
		var first_subarray: Array[Int] = Array.fill[Int](s1)(0);
		var second_subarray: Array[Int] = Array.fill[Int](s2)(0);
		//  Loop controlling variables
		var i: Int = 0;
		var j: Int = 0;
		var counter: Int = 0;
		//  Get the elements of first subarray
		while (i < s1)
		{
			first_subarray(i) = auxiliary(front + i);
			i += 1;
		}
		//  Get the elements of second subarray
		i = 0;
		while (i < s2)
		{
			second_subarray(i) = auxiliary(middle + i + 1);
			i += 1;
		}
		i = 0;
		//   Add sorted elements into actual array
		while (counter < s1 + s2)
		{
			//  Check that both sub array element exists or not
			if (i < s1 && j < s2)
			{
				if (first_subarray(i) <= second_subarray(j))
				{
					//  When first array [i] element are smaller
					auxiliary(front + counter) = first_subarray(i);
					i += 1;
				}
				else
				{
					//  When second array [j] element are smaller
					auxiliary(front + counter) = second_subarray(j);
					j += 1;
				}
			}
			else if (i < s1)
			{
				//  When first sub array element exists
				auxiliary(front + counter) = first_subarray(i);
				i += 1;
			}
			else
			{
				//  When second sub array element exists
				auxiliary(front + counter) = second_subarray(j);
				j += 1;
			}
			counter += 1;
		}
	}
	//  Split the array elements into two parts
	def sort_element(auxiliary: Array[Int], front: Int, tail: Int): Unit = {
		if (front < tail)
		{
			//  Get middle location of given index
			var middle: Int = ((front + tail) / 2).toInt;
			//  Split the array into two parts
			this.sort_element(auxiliary, front, middle);
			this.sort_element(auxiliary, middle + 1, tail);
			//  Combine split array into sorted way
			this.merge_elements(auxiliary, front, tail, middle);
		}
	}
	def update_element(row: Int, 
                       col: Int, 
                       matrix: Array[Array[Int]], 
      					auxiliary: Array[Int], 
        				s_row: Int, s_col: Int, 
                      e_row: Int, e_col: Int, 
                        s: Int): Unit = {
        var size = s;
		//  Left to right
		var i: Int = s_col;
		while (i <= e_col && size > 0)
		{
			matrix(s_row)(i) = auxiliary(row * col - size);
			size = size - 1;
			i += 1;
		}
		//  Top to down
		i = s_row + 1;
		while (i <= e_row && size > 0)
		{
			matrix(i)(e_col) = auxiliary(row * col - size);
			size = size - 1;
			i += 1;
		}
		//  Bottom right to bottom-left
		i = e_col - 1;
		while (i >= s_col && size > 0)
		{
			matrix(e_row)(i) = auxiliary(row * col - size);
			size = size - 1;
			i -= 1;
		}
		//  Bottom left to top
		i = e_row - 1;
		while (i > s_row && size > 0)
		{
			matrix(i)(s_row) = auxiliary(row * col - size);
			size = size - 1;
			i -= 1;
		}
		if (s_row + 1 <= e_row - 1 && size > 0)
		{
			//  Recursive call
			this.update_element(row, col, matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size);
		}
	}
	def sorted_spiral(row: Int, col: Int, matrix: Array[Array[Int]]): Unit = {
		var size: Int = row * col;
		if (size <= 0)
		{
			return;
		}
		var auxiliary: Array[Int] = Array.fill[Int](size)(0);
		var i: Int = 0;
		var j: Int = 0;
		var k: Int = 0;
		//   Collect elements of 2d array
		while (i < row)
		{
			j = 0;
			while (j < col)
			{
				auxiliary(k) = matrix(i)(j);
				k += 1;
				j += 1;
			}
			i += 1;
		}
		this.sort_element(auxiliary, 0, size - 1);
		this.update_element(row, col, matrix, auxiliary, 0, 0, row - 1, col - 1, size);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyMatrix = new MyMatrix();
		//   Define matrix of integer elements
		var matrix: Array[Array[Int]] = Array(
          Array(4, 6, 2, 2), 
          Array(3, 7, 6, 5), 
          Array(1, 5, 6, 6), 
          Array(5, 5, 4, 8), 
          Array(1, 5, 12, 9), 
          Array(7, 5, 2, 3), 
          Array(1, 9, 8, 10));
		var row: Int = matrix.length;
		var col: Int = matrix(0).length;
		print("\n Before sorted spiral\n");
		obj.print_matrix(row, col, matrix);
		obj.sorted_spiral(row, col, matrix);
		print("\n After sorted spiral\n");
		obj.print_matrix(row, col, matrix);
	}
}

Output

 Before sorted spiral
  4  6  2  2
  3  7  6  5
  1  5  6  6
  5  5  4  8
  1  5  12  9
  7  5  2  3
  1  9  8  10


 After sorted spiral
  1  1  1  2
  6  6  6  2
  6  12  7  2
  5  10  7  3
  5  9  8  3
  5  9  8  4
  5  5  5  4

/*
    Swift 4 program 
    Convert given Matrix into sorted Spiral Matrix
*/
//   Define TreeNode
class MyMatrix
{
	//  Displaying of the matrix elements
	func print_matrix(_ row: Int, _ col: Int, _ matrix: [[Int]])
	{
		var i: Int = 0;
		while (i < row)
		{
			var j: Int = 0;
			while (j < col)
			{
				print("  ", matrix[i][j], terminator: "");
				j += 1;
			}
			print("\n", terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
	//  Sorted merge of given two subarrays of an array
	func merge_elements(_ auxiliary: inout[Int], _ front: Int, _ tail: Int, _ middle: Int)
	{
		//  Get the size of first subarray
		let s1: Int = (middle - front) + 1;
		//  Get the size of second subarray
		let s2: Int = tail - middle;
		//  Creating auxiliary storage to store elements
		var first_subarray: [Int] = Array(repeating: 0, count: s1);
		var second_subarray: [Int] = Array(repeating: 0, count: s2);
		//  Loop controlling variables
		var i: Int = 0;
		var j: Int = 0;
		var counter: Int = 0;
		//  Get the elements of first subarray
		while (i < s1)
		{
			first_subarray[i] = auxiliary[front + i];
			i += 1;
		}
		//  Get the elements of second subarray
		i = 0;
		while (i < s2)
		{
			second_subarray[i] = auxiliary[middle + i + 1];
			i += 1;
		}
		i = 0;
		//   Add sorted elements into actual array
		while (counter < s1 + s2)
		{
			//  Check that both sub array element exists or not
			if (i < s1 && j < s2)
			{
				if (first_subarray[i] <= second_subarray[j])
				{
					//  When first array [i] element are smaller
					auxiliary[front + counter] = first_subarray[i];
					i += 1;
				}
				else
				{
					//  When second array [j] element are smaller
					auxiliary[front + counter] = second_subarray[j];
					j += 1;
				}
			}
			else if (i < s1)
			{
				//  When first sub array element exists
				auxiliary[front + counter] = first_subarray[i];
				i += 1;
			}
			else
			{
				//  When second sub array element exists
				auxiliary[front + counter] = second_subarray[j];
				j += 1;
			}
			counter += 1;
		}
	}
	//  Split the array elements into two parts
	func sort_element(_ auxiliary: inout [Int], _ front: Int, _ tail: Int)
	{
		if (front < tail)
		{
			//  Get middle location of given index
			let middle: Int = (front + tail) / 2;
			//  Split the array into two parts
			self.sort_element(&auxiliary, front, middle);
			self.sort_element(&auxiliary, middle + 1, tail);
			//  Combine split array into sorted way
			self.merge_elements(&auxiliary, front, tail, middle);
		}
	}
	func update_element(_ row: Int,
                        _ col: Int, _ matrix: inout[[Int]], 
      _ auxiliary:inout [Int], _ s_row: Int,
        _ s_col: Int, _ e_row: Int,
          _ e_col: Int, _ s:  Int)
	{
      	var size = s;
		//  Left to right
		var i: Int = s_col;
		while (i <= e_col && size > 0)
		{
			matrix[s_row][i] = auxiliary[row * col - size];
			size -= 1;
			i += 1;
		}
		//  Top to down
		i = s_row + 1;
		while (i <= e_row && size > 0)
		{
			matrix[i][e_col] = auxiliary[row * col - size];
			size -= 1;
			i += 1;
		}
		//  Bottom right to bottom-left
		i = e_col - 1;
		while (i >= s_col && size > 0)
		{
			matrix[e_row][i] = auxiliary[row * col - size];
			size -= 1;
			i -= 1;
		}
		//  Bottom left to top
		i = e_row - 1;
		while (i > s_row && size > 0)
		{
			matrix[i][s_row] = auxiliary[row * col - size];
			size -= 1;
			i -= 1;
		}
		if (s_row + 1 <= e_row - 1 && size > 0)
		{
			//  Recursive call
			self.update_element(row, col, &matrix, &auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size);
		}
	}
	func sorted_spiral(_ row: Int, _ col: Int, _ matrix: inout[[Int]])
	{
		let size: Int = row * col;
		if (size <= 0)
		{
			return;
		}
		var auxiliary: [Int] = Array(repeating: 0, count: size);
		var i: Int = 0;
		var j: Int = 0;
		var k: Int = 0;
		//   Collect elements of 2d array
		while (i < row)
		{
			j = 0;
			while (j < col)
			{
				auxiliary[k] = matrix[i][j];
				k += 1;
				j += 1;
			}
			i += 1;
		}
		self.sort_element(&auxiliary, 0, size - 1);
		self.update_element(row, col, &matrix, &auxiliary, 0, 0, row - 1, col - 1, size);
	}
}
func main()
{
	let obj: MyMatrix = MyMatrix();
	//   Define matrix of integer elements
	var matrix: [[Int]] = [
		[4, 6, 2, 2] , 
        [3, 7, 6, 5] , 
        [1, 5, 6, 6] , 
        [5, 5, 4, 8] , 
        [1, 5, 12, 9] , 
        [7, 5, 2, 3] , 
        [1, 9, 8, 10]
	];
	let row: Int = matrix.count;
	let col: Int = matrix[0].count;
	print("\n Before sorted spiral\n", terminator: "");
	obj.print_matrix(row, col, matrix);
	obj.sorted_spiral(row, col, &matrix);
	print("\n After sorted spiral\n", terminator: "");
	obj.print_matrix(row, col, matrix);
}
main();

Output

 Before sorted spiral
   4   6   2   2
   3   7   6   5
   1   5   6   6
   5   5   4   8
   1   5   12   9
   7   5   2   3
   1   9   8   10


 After sorted spiral
   1   1   1   2
   6   6   6   2
   6   12   7   2
   5   10   7   3
   5   9   8   3
   5   9   8   4
   5   5   5   4

/*
    Kotlin program 
    Convert given Matrix into sorted Spiral Matrix
*/
//   Define TreeNode
class MyMatrix
{
	//  Displaying of the matrix elements
	fun print_matrix(row: Int, col: Int, matrix: Array < Array < Int >> ): Unit
	{
		var i: Int = 0;
		while (i < row)
		{
			var j: Int = 0;
			while (j < col)
			{
				print("  " + matrix[i][j]);
				j += 1;
			}
			print("\n");
			i += 1;
		}
		print("\n");
	}
	//  Sorted merge of given two subarrays of an array
	fun merge_elements(auxiliary: Array < Int > , front: Int, tail: Int, middle: Int): Unit
	{
		//  Get the size of first subarray
		var s1: Int = (middle - front) + 1;
		//  Get the size of second subarray
		var s2: Int = tail - middle;
		//  Creating auxiliary storage to store elements
		var first_subarray: Array < Int > = Array(s1)
		{
			0
		};
		var second_subarray: Array < Int > = Array(s2)
		{
			0
		};
		//  Loop controlling variables
		var i: Int = 0;
		var j: Int = 0;
		var counter: Int = 0;
		//  Get the elements of first subarray
		while (i < s1)
		{
			first_subarray[i] = auxiliary[front + i];
			i += 1;
		}
		//  Get the elements of second subarray
		i = 0;
		while (i < s2)
		{
			second_subarray[i] = auxiliary[middle + i + 1];
			i += 1;
		}
		i = 0;
		//   Add sorted elements into actual array
		while (counter < s1 + s2)
		{
			//  Check that both sub array element exists or not
			if (i < s1 && j < s2)
			{
				if (first_subarray[i] <= second_subarray[j])
				{
					//  When first array [i] element are smaller
					auxiliary[front + counter] = first_subarray[i];
					i += 1;
				}
				else
				{
					//  When second array [j] element are smaller
					auxiliary[front + counter] = second_subarray[j];
					j += 1;
				}
			}
			else
			if (i < s1)
			{
				//  When first sub array element exists
				auxiliary[front + counter] = first_subarray[i];
				i += 1;
			}
			else
			{
				//  When second sub array element exists
				auxiliary[front + counter] = second_subarray[j];
				j += 1;
			}
			counter += 1;
		}
	}
	//  Split the array elements into two parts
	fun sort_element(auxiliary: Array < Int > , front: Int, tail: Int): Unit
	{
		if (front < tail)
		{
			//  Get middle location of given index
			var middle: Int = (front + tail) / 2;
			//  Split the array into two parts
			this.sort_element(auxiliary, front, middle);
			this.sort_element(auxiliary, middle + 1, tail);
			//  Combine split array into sorted way
			this.merge_elements(auxiliary, front, tail, middle);
		}
	}
	fun update_element(row: Int, col: Int, 
                       matrix: Array <Array<Int>> , 
                       auxiliary: Array < Int > , 
                       s_row: Int, s_col: Int, 
                       e_row: Int, e_col: Int,
                       s: Int): Unit
	{
      	var size = s;
		//  Left to right
		var i: Int = s_col;
		while (i <= e_col && size > 0)
		{
			matrix[s_row][i] = auxiliary[row * col - size];
			size = size - 1;
			i += 1;
		}
		//  Top to down
		i = s_row + 1;
		while (i <= e_row && size > 0)
		{
			matrix[i][e_col] = auxiliary[row * col - size];
			size = size - 1;
			i += 1;
		}
		//  Bottom right to bottom-left
		i = e_col - 1;
		while (i >= s_col && size > 0)
		{
			matrix[e_row][i] = auxiliary[row * col - size];
			size = size - 1;
			i -= 1;
		}
		//  Bottom left to top
		i = e_row - 1;
		while (i > s_row && size > 0)
		{
			matrix[i][s_row] = auxiliary[row * col - size];
			size = size - 1;
			i -= 1;
		}
		if (s_row + 1 <= e_row - 1 && size > 0)
		{
			//  Recursive call
			this.update_element(row, col, matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size);
		}
	}
	fun sorted_spiral(row: Int, col: Int, matrix: Array < Array < Int >> ): Unit
	{
		var size: Int = row * col;
		if (size <= 0)
		{
			return;
		}
		var auxiliary: Array < Int > = Array(size)
		{
			0
		};
		var i: Int = 0;
		var j: Int ;
		var k: Int = 0;
		//   Collect elements of 2d array
		while (i < row)
		{
			j = 0;
			while (j < col)
			{
				auxiliary[k] = matrix[i][j];
				k += 1;
				j += 1;
			}
			i += 1;
		}
		this.sort_element(auxiliary, 0, size - 1);
		this.update_element(row, col, matrix, auxiliary, 0, 0, row - 1, col - 1, size);
	}
}
fun main(args: Array < String > ): Unit
{
	var obj: MyMatrix = MyMatrix();
	//   Define matrix of integer elements
	var matrix: Array<Array<Int>> = arrayOf(
      arrayOf(4, 6, 2, 2), 
      arrayOf(3, 7, 6, 5), 
      arrayOf(1, 5, 6, 6), 
      arrayOf(5, 5, 4, 8), 
      arrayOf(1, 5, 12, 9), 
      arrayOf(7, 5, 2, 3), 
      arrayOf(1, 9, 8, 10));
	var row: Int = matrix.count();
	var col: Int = matrix[0].count();
	print("\n Before sorted spiral\n");
	obj.print_matrix(row, col, matrix);
	obj.sorted_spiral(row, col, matrix);
	print("\n After sorted spiral\n");
	obj.print_matrix(row, col, matrix);
}

Output

 Before sorted spiral
  4  6  2  2
  3  7  6  5
  1  5  6  6
  5  5  4  8
  1  5  12  9
  7  5  2  3
  1  9  8  10


 After sorted spiral
  1  1  1  2
  6  6  6  2
  6  12  7  2
  5  10  7  3
  5  9  8  3
  5  9  8  4
  5  5  5  4

Output Explanation

The given Java code implements the above algorithm to convert the given matrix into a sorted spiral matrix. It prints the original matrix and the sorted spiral matrix.

Time Complexity

The time complexity of the provided solution is O(row * col * log(row * col)), where 'row' is the number of rows and 'col' is the number of columns in the 2D matrix. The function traverses all the elements of the matrix once to collect them in the auxiliary array, which takes O(row * col) time. Then, the merge sort is applied to the auxiliary array, which has a time complexity of O(row * col * log(row * col)). Finally, the elements from the sorted auxiliary array are updated back into the matrix, which takes O(row * col) time. Therefore, the overall time complexity is dominated by the sorting step.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment