Sorting by placement and shift

摘要

In sorting situations where the final destination of each item is known, it is natural to repeatedly choose items and place them where they belong, allowing the intervening items to shift by one to make room. (In fact, a special case of this algorithm is commonly used to hand-sort files.) However, it is not obvious that this algorithm necessarily terminates.