Robot sort:
You have boxes in magazine and a single empty spot (at the end) like:

1, 4, 2, 5, 3, _

You have a robot which needs to sort boxes. It can only pick up single box, put it in empty box and then pick another one up. Sort boxes to have either _, 1, 2, 3, 4, 5 or 1, 2, 3, 4, 5, _
What is the fastest way to sort if robot knows immediately where are boxes with specific numbers, but it takes time for him to move.

I provided 2 solutions: selection sort, to always put correct element in empty spot since we know where everything is, but it still is O(n^2) and seems to unnecessarily jump over other elements, which doesn't seem optimal or some version of insertion / bubble sort, although it was difficult with only 1 empty spot, to shift elements. I don't know what is correct solution.

Edit:
This graph solutions proposed here are quite a good idea, but what is their complexity? Obviously we won't generate whole graph as it would be O(n!) but is it better than simple selection sort with O(n^2)?