<p>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?</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-08-16T20:50:09.573Z
In short, you can do an sqrt(N)-way merge, like in mergesort? That was my running best method, but it turns out to be O(N log N)--I don't have an exact constant there, but there's a 0.5 for log(sqrt(N)) at least.
Zachary Vance
CC BY-SA 2.5
2010-08-16T20:11:04.240Z
2010-08-16T20:42:03.493Z
2010-08-16T20:42:03.493Z
Paul
<p>It's easy to prove an Ω(n<sup>2</sup> log n) lower bound on this problem (in the comparison sorting model): if the element at position (i,j) is always within distance 1/2 of i+j, then the grid diagonals are independent of each other, and the sorted order within each grid diagonal is arbitrary. So under this constraint the total number of orderings possible is the product (over all the diagonals of the grid) of the factorials of the lengths of the diagonals, which is exponential in n<sup>2</sup> log n.</p>

<p>Which is to say that standard comparison sorting algorithms are asymptotically optimal for grids ordered as you describe.</p>

CC BY-SA 2.5
2010-08-16T20:54:45.337Z
The other answer gives an explicit algorithm with this complexity, so I'll consider this problem solved for 2-D grids and, without actually checking, probably for arbitrary dimension grids.
Zachary Vance
CC BY-SA 2.5
2010-08-16T20:40:01.720Z
2010-08-16T20:40:01.720Z
David Eppstein
<p>I have a dataset which is a number of objects arranged in a 2-D grid.  I know I have a strict ordering, increasing as you go left-to-right within each row, and increasing as top-to-bottom within each column.  For example, </p>

<ul>
<li>1 2 3</li>
<li>4 6 7</li>
<li>5 8 9</li>
</ul>

<p>Can I improve on naive sorting to sort the entire dataset linearly (as measured in comparisons)?</p>

<p>What about for n-d datasets?  Arbitrary finite datasets with a subset of comparisons known?</p>

CC BY-SA 2.5
2010-08-16T19:56:53.447Z
Can you ask a more precise question?  Your first paragraph can be read to imply that your data is already sorted!  What exactly is your input, and what output do you wish?
Jacques Carette
CC BY-SA 2.5
2010-08-16T20:02:44.430Z
Yes, that's what I meant.  I will edit for clarity.
Zachary Vance
<ds.algorithms><total-ordering><sorting>
What is a good special-case sorting algorithm?
Zachary Vance
# What is a good special-case sorting algorithm?

(Asked by: username_0 on 2010-08-16)

I have a dataset which is a number of objects arranged in a 2-D grid. I know I have a strict ordering, increasing as you go left-to-right within each row, and increasing as top-to-bottom within each column. For example,

* 1 2 3
* 4 6 7
* 5 8 9

Can I improve on naive sorting to sort the entire dataset linearly (as measured in comparisons)?

What about for n-d datasets? Arbitrary finite datasets with a subset of comparisons known?

**Tags:** ds.algorithms, total-ordering, sorting
> **Comments:**
> **username_1**: Can you ask a more precise question?  Your first paragraph can be read to imply that your data is already sorted!  What exactly is your input, and what output do you wish?  
> **username_0**: Yes, that's what I meant.  I will edit for clarity.  

---

## 2 answers

### Answer by username_3 on 2010-08-16. Score: 19 | Accepted answer

It's easy to prove an Ω(n2 log n) lower bound on this problem (in the comparison sorting model): if the element at position (i,j) is always within distance 1/2 of i+j, then the grid diagonals are independent of each other, and the sorted order within each grid diagonal is arbitrary. So under this constraint the total number of orderings possible is the product (over all the diagonals of the grid) of the factorials of the lengths of the diagonals, which is exponential in n2 log n.

Which is to say that standard comparison sorting algorithms are asymptotically optimal for grids ordered as you describe.

> **Comments:**
> **username_0**: The other answer gives an explicit algorithm with this complexity, so I'll consider this problem solved for 2-D grids and, without actually checking, probably for arbitrary dimension grids.  

---

### Answer by username_2 on 2010-08-16. Score: 4

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.

> **Comments:**
> **username_0**: In short, you can do an sqrt(N)-way merge, like in mergesort? That was my running best method, but it turns out to be O(N log N)--I don't have an exact constant there, but there's a 0.5 for log(sqrt(N)) at least.  

---

