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