CareerCup

Note that a standard sorting algorithm can do what you want.

You can simply sort the n^2 array in Ω(n^2 log n^2) time with merge sort, and note that Ω(n ^2 log n^2) = 2 n^2 log n is Ω(n^2 log n) as required.

Correct its just sorting n^2 elements you can use merge sort with complexity ( n^2 Log n^2) which is 2*n^2Logn

1. Sort the array first.
2. Assign the value of the sorted result one by one starting from the first one to the result 2-d array diagonally starting from the top-left cell.

Time complexity for 1st step is n^2*log(n^2) = 2*n^2log(n), and 2nd step costs n^2. Thus, the overall cost is O(n^2log(n)).

I guess the question is to output a matrix where both rows and column are sorted. To do that
1) Sort the n^2 elements O(n^2 logn)
2) Make the first n elements as first row, next n elements as 2nd row.....
Other matrix combinations can be formed by using the below logic
1) Choose a value of increment d <n
2) Pick up the elements of a row in increments of d e.g.
row 1: 1, 1+d, 1+2d....
row 2: 2, 2+d, 2+2d....

for(i=1;i<=n;i++)
	{ for(j=i;j<=n^2;j+=d)
		print A[j]
	 print "\n"
	}

If use a sorting then we have an sorted array for O(n^2 log n), so filling matrix by rows or by columns gets as result a sorted matrix by columns and rows.
But If we know about the range of numbers that it's a sequence then we can get sorted matrix by calculating an row and column indexes by number in the sequence for O(n).

in c++ sort with anything and just treat it like a 2-d array. you are done.

if it is fixed in the sense that the values are always 1-n, we can print it in linear time

Well, lets imagine that matrix is linear array divided into N equal parts where each part represents row in the matrix. Now imagine that this linear array is sorted and we try to write it to the matrix level by level. If array is sorted it means that if we write it into a matrix level by level then each row in the matrix is sorted and each column is sorted as well. This is because previous level is always closer to the beginning of array and since our array is sorted it means that every element in previous level is less then every element in the next one.
We want to avoid situation with big memory complexity. To do so we can can introduce function that acts as if it would transfered matrix to the linear array and got its ith element. something like

get(int i, int matrix[][]

This is useful because using this function we are able to sort array just with any normal sort that uses index access to elements.
This function looks pretty easy actually:

//assume that matrix is square
int get(int index, int matrix[][]) {
    return matrix[index/matrix.length][index%matrix.length];
}
int get(int index, int matrix[][]) {
    return matrix[index/matrix.length][index%matrix.length];
}

int get(int index, int matrix[][]) {
    return matrix[index/matrix.length][index%matrix.length];
}

int get(int index, int matrix[][]) {
    return matrix[index/matrix.length][index%matrix.length];
}

int set(int index, int matrix[][], int value) {
     matrix[index/matrix.length][index%matrix.length] = value;
}

using this two functions we can use some O(nlogn) sort. But since we are using O(n) get sorting this array will cost us O(n^2 logn)

How about thinking of the n^2 array already as a 2d array. Then, all the code would have to do is execute a single sort on each of the columns (that would be expected O(n^2 log n) if using a QuickSort) and sort each row (that would also be O(n^2 log n) ). Then entire sort would be effectively O(n^2 log n). This would be significantly better than O(n^2 Log n^2).