It may be linear in the number of items, but not in the number of rightful places (you’d have to sort the items by rightful place first). Deciding on each rightful place also tends to not be constant-time.
On the bright side, at least the rightful places are presumably still in Euclidean space so there are efficient solutions for the optimal traversal paths.
