Sorting by placement and shift
Sergi Elizalde, Peter M. Winkler · 2009
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. We show that in fact the algorithm terminates after at most 2n−1−1 steps in the worst case (confirming a conjecture of L. Larson), and that there are super-exponentially many per-mutations for which this exact bound can be achieved. The proof involves a curious symmetrical binary representation. 1 The Problem Suppose that a permutation pi ∈ Sn is fixed and repre-sented by the sequence pi(1),..., pi(n). Any number i with pi(i) 6 = i may be “placed ” in its proper position, with the numbers in positions between i and pi(i) shifted up or down as necessary. Repeatedly placing numbers until the identity permutation is achieved constitutes a process we call homing. One might imagine that the numbers are written on billiard balls in a trough, as in Figure 1 below, where the shift is a natural result of moving a ball to a new position.