What is a good special-case sorting algorithm? 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?
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.