Moving sort elements could be expensive for at least two reasons. The first is expensive copying operations, as would be the case for large object instances. For linked lists, however, the sort elements are pointed to, and moving pointers around is about as efficient as you can get.
The second source of expense, the one relevant to linked lists, is finding the locations participating in the move. Linked lists require O(n) link traversals to set the source and target destinations. While not as expensive as moving around big fat class instances, traversing links is an expense not incurred (or incurred more cheaply) by indirect sorting.
This page last modified on 24 January 2006.