If I understand the problem correctly (and I may not, feel free to tell me if I don't) you want to transform a 2D grid into a sorted 1D array, whereas each row and column is already sorted in the 2D grid?
The first element in the list in this case has to be the top-left corner ((0,0), by definition of the problem). After this it has to either be the (1,0) or (0,1) element, as all others will be larger than these by definition.
You can generalise by saying that the next smallest element in the grid is always directly below an element already used (or the edge of grid), and also to the right of an element already used (or the edge of grid), since both are defined to be smaller than it.
So at each iteration you must only consider the smallest value that fulfills this requirement.
You can keep the possible candidates in sorted order as you find them (no more than two will ever be made available in one iteration), and at each iteration check the new values made available (if any).
If they're lower than the lowest of the previous candidates add them to the list straight away and repeat, otherwise add the lowest previous candidate and compare to the next lowest etc.
Unfortunately I don't claim to be able to provide an exact complexity of this, nor do I claim it's the most efficient possible, it certainly seems better than a naive approach, and I hope I explained it well enough for you to understand.
EDIT: For n-d grids like this I believe the same basic principle applies, but each iteration makes up to n new candidates available, and these candidates must be the smallest unused elements in each of n dimensions at this point.