Sorting by Placement and ShiftSergi Elizalde∗Peter Winkler†June 26, 2008AbstractIn sorting situations where the final destination of each item is known, it is natural torepeatedly choose items and place them where they belong, allowing the intervening itemsto shift by one to make room. (In fact, a special case of this algorithm is commonly usedto ha nd- 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 worstcase (confirming a conjecture of L. Larson), and that there are super-exponentially manypermutatio ns for which this exact bound can be achieved. The proof involves a curioussymmetrical binar y representation.1 The ProblemSuppose that a permutation π ∈ Snis fixed and represented by the sequ en ce π(1), . . . , π(n).Any number i with π(i) 6= i may be “placed” in its proper position, with the numbers inpositions between i and π(i) shifted up or down as necessary. Repeatedly placing numbersuntil the identity permutation is achieved constitutes a process we call homing. One mightimagine that the numbers are written on billiard balls in a trough, as in Figure 1 below, wherethe shift is a natural result of moving a b all to a new position.1 23 45 6 78123456 781 23456 78Figure 1: Two steps in homing∗Department of Mathematics, Dartmouth, Hanover NH 03755-3551, USA; [email protected].†Department of Mathematics, Dartmouth, Hanover NH 03755-3551, USA; [email protected] be precise, if π(i) > i and i is placed, the resu lting permutation π′is given byπ′(j) =π(j) if π(j) < i or π(j) > π(i)i if j = iπ(j)−1 if i < π(j) < π(i)and if π(i) < i, we haveπ′(j) =π(j) if π(j) < π(i) or π(j) > ii if j = iπ(j)+1 if π(i) < j < iThe primary question we answer is: how many steps does homing take in the worst case?2 HistoryDespite its s implicity, homing seems not to have been considered before in the literature; itarose recently as a result of a misunderstandin g (details below). It is, of course, only in aloose sense a sorting algorithm at all, since it requires that the final position of each item beknown, and presumes that it is desirable to sort “in place.” Thu s, it makes sense primarilyfor physical obj ects. Nonetheless, one can imagine a situation where a huge linked list is tobe sorted in response to on-line information about where items ultimately belong; then it mayseem reasonable to place items as information is received, allowing the items between to shiftup or down by one. W e do not recommend this procedure!In hand-sorting files, it is common to find the alphabetically first file and move it to thefront, then find the alphabetically second file and move it to the position behind the first file,et cetera. This is a (fast) special case of homing.Homing was brought to our attention by mathematician an d reporter Barry Cipra [2]. Cip rahad been looking at John H. Conway’s “Topswops” algorithm [4], in which only the leftmostnumber is placed and intervening numbers are reversed. Topswops terminates when the 1 isin position, even if the rest of the numbers are still scrambled. Seeking to get everything inorder, C ipra considered allowing any not-at-home number to be placed, again reversing the in-tervening numbers. This algorithm does not necessarily terminate, however; a cycling example(71325684→ 71348652 → 56843172 → 52713486 → 52317486 → 71325486 → 71325684) wasprovided to Cipra by David Callan, of the University of Wisconsin [1].When Cipra tried to explain his interest to his friend Loren Larson (co-author of TheInquisitive Problem Solver [7]) the latter thought that the intervening items were to be shifted.Cipra liked the new procedure, especially as he was able to show it did always terminate, anddesigned a game around it. The game involved sorting vertical strips of famous paintin gs (suchas Picasso’s Guernica); Cipra called it “PermutARTions.” A prototype of the game, renamed“Picture Th is,” has since been made by puzzle designer O skar van Deventer.The neatest proof known to us that homing always terminates is due to Noam E lkies [3].Since there are only finitely many states, non-termination would imply the existence of a cycle;let k be the largest number which is placed upward in the cycle. (If no number is placedupward, the lowest number placed downward is used in a symmetric argument). Once k isplaced, it can be dislodged upward and placed again dow nward, but nothing can ever push itbelow position k. Hence it can never again be placed upward, a contradiction.23 OutlineIn Section 4 we will consider fast homing, that is, the minimum number of steps needed to sortfrom a given permutation π. Among other th ings we will see that homing can always be donein at most n−1 steps (with a single worst-case example), and that there is an easy sequ en ceof choices which r espects that bound.In Section 5 we prove that homing cannot take more than 2n−1−1 steps; in Section 6, weshow that there are super-exponentially many permutations which can support exactly 2n−1−1steps.Finally, in Section 7, we wrap up and conclude with some open questions.4 Fast HomingA placement of either the least or the greatest number not currently in its home will be calledextremal; such a nu mber i will never subsequently be dislodged from its home, since no othernumber will ever cross i on its way. Hence,Theorem 4.1. Any algorithm that always places the smallest or large st available number willterminate in at most n−1 steps.Proof. After n−1 numbers are home, the nth must be as well.The algorithm which places the smallest not-at-home number is th e one cited above, oftenused to hand-sort files. The precise number of steps requir ed is the smallest j such that thefiles which belong in positions j+1, j+2, . . . , n are already in the correct order.Suppose placements are random, that is, at each step a uniformly random number is chosenfrom among those that are not at home and then placed. Let us say that a permutation isin “stage k” if k (b ut not k+1) of the extremal numbers are home; thus, e.g., 1,2,3,7,4,6,5,8,9is in stage 5, since 1, 2, 3, 8 and 9 are home. There is no stage n −1. If π is in stage k, fork < n, then with probability at least 2/(n−k), the next placement will leave it in stage k+1or higher. It follows that the expected number of p lacements needed to