Is it always possible to order a multi-dimensional array in all dimensions? How?

Question

Suppose, I have an n-dimensional array of integers (for n=1 it's a vector, for n=2 it's a rectangular matrix, for n=3 it's a parallelepiped, etc). I need to reorder elements of the array so that elements in each row, column, etc are in a non-decreasing order.

• Is it possible for any input array?
• Is the required ordering unique for any input array? I just realized that the answer for this question in general is no, e.g. for square matrices.
• Is the required ordering unique for any input array that has different lengths in all dimensions?
• What is the fastest algorithm to produce the required ordering?

Answer 1

Is it possible for any input array?

Yes, if we will look on the array as a single dimension array, with the same number of elements, and then sort it, by traversing it back to the original n-dimensions array, it remains sorted, since for each i1,....,i_k,...,i_m: for all i_k < i_k':

i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k) + ... < i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k') + ...
Thus (the array is ordered):
arr[i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k) + ...] < arr[ i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k') + ...]
Thus (back to original array):
arr[i_1][i_2]...[i_k]... < arr[i_1][i_2]...[i_k']...

As for the 2nd question:

Is the required ordering unique for any input array that has different lengths in all dimensions?

No:

1 1          1 3
3 4          1 4
5 6          5 6

What is the fastest algorithm to produce the required ordering?

One solution is suggested already: regard it is a big long array and sort it. Complexity is O(n_1*n_2*...*n_m*log(n_1*n_2*...*n_m))
My gut says if you could do it faster, you could sory faster then O(nlogn), but I have no proof for this claim, so it might be wrong.

Answer 2

Let me elaborate more about Alptigin Jalayr's idea.

Suppose we have rows sorted, so for the following data, we have a <= b and c <= d.

     .       .
..., a, ..., b, ...
     .       .
..., c, ..., d, ...
     .       .

When a is greater than c, i.e. c <a, then swap of them gives us c < b since a <= b, and a <=d since b <= d (if b > d, we swap b and d as well). In a word, sorting rows first and then columns next can give you the desired matrix.