I'll be very interested to see a real answer for this. This is a tough problem.
I propose that we first figure out the sorted order, which we can do without touching the stones. Now, consider the worst case: the stones are in reverse-sorted order. The minimum distance required to move the stones to the correct positions is greater than $d(n-1) + d(n-2) + ... + d(n/2-1) + ... + d(n-2) + d(n-1)$ which is going to be $O(n^2)$ in the number of stones to sort. There is no sorting algorithm that will move stones such that the worst-case efficiency is any better than quadratic (under some assumptions, see below).
Given that, consider the dumbest algorithm imaginable:
- Figure out the sorted order
- Slide stones up, over, then up, one at a time, to put them in sorted order two squares above the original row.
- Slide each stone down two squares.
Here, the horizontal sliding distance is optimal (assuming stones must return to the original row; if this is not actually required, the problem becomes significantly more interesting). We pay a tax of 4 moves per stone, $O(n)$ overhead, which is eaten by the $O(n^2)$ term in the worst case. The extra distance for moving vertically is $8rn$, or $80$ squares for the $n=20$ case, where the minimal distance in the worst case is at least about $380$. The number of squares would be $4000$ for the $n=1000$ case, where the minimal distance in the worst case is about $999,000$.
It seems likely that any workable algorithm (that returns stones to the original row, at least) is going to need to pay a tax of at least $\pi r - 2r$, or about $1.14r$, for round stones of cross-sectional radius $r$ that can rotate around each other, or $s$ for square stones of cross-sectional side $s$ that slide around each other on a grid.
There are some heuristics you can use to make the runtimes better in some cases, but I doubt whether there's a method to get around the $O(n^2)$ required for horizontal distances (unless we're allowed to line the stones up somewhere else, in which case this becomes more challenging).
(If the question is about finding a real procedure that gets the vertical move tax down as close to optimal as possible, that's something we can also discuss, but it will be useful to frame the question in those terms if that's the case. Even the dumb algorithm above can be modified so that in cases other than the worst, performance is significantly better).