Sorting pairs in bins (2004)

Originators: Peter Winkler    (presented by Douglas West - REGS 2008)

Background: Balls labeled 1 through n are placed in some order into bins labeled 1 through n. One wants to move each ball to the bin with its label. The allowable operation is to exchange the balls in two adjacent bins. Assume that the bins are labeled in increasing order from left to right. Any permutation can be sorted in n(n-1)/2 exchanges ("bubble sort"). There is no better bound, because when the balls start in reverse order each ball must be exchanged with every other to complete the sorting.

Suppose instead that there are two balls with each label, two in each bin, starting with the two balls labeled i in the bin labeled n+1-i. Certainly n(n-1) exchanges suffice to move each ball to its own bin, but this is not optimal. When n=3, the sorting can be done in 5 moves. Winkler [W] poses the problem of finding the minimum number of moves and reports that a German publishing company has offered 1000 euros for an optimal algorithm.

Conjecture: The optimal number of moves is asymptotic to (2/3)n².

Comments: Winkler observes that n(2n-1)/3 is a lower bound. For each of the 2n(2n-1)/2 pairs of balls, we count 1, as follows. Balls with different labels must exchange positions; we count one if we do this by exchanging them, or ½ when they first come together and ½ when they last separate in the desired order. Balls with the same label must separate during the process and return together; we count ½ for each of these events. On each exchange, the pair we exchange can gain 1, the two pairs we split by starting the exchange can contribute ½ each, and the two pairs we form by completing the exchange can contribute ½ each. Hence we obtain at most 3 toward the total required count with each move. When n=6, this lower bound says that at least 22 moves are needed, but this is not achievable; computer search shows that 23 are needed.

When n=5, the sorting can be done in 15 moves. In REGS 2008, Stocker observed that one can use this recursively to obtain an upper bound of (4/5)n². Nevertheless, a very simple algorithm suggested by Stocker and West seems to complete the sorting with a number of moves asymptotic to the lower bound. With n over 100,000, the number of moves taken by this algorithm is less than 1.03 times the lower bound. the algorithm takes the leftmost ball of largest label that is out of position and exchanges it with the lower-labeled ball in the bin to its right. Repeat.

References:
[P] Peter Winkler, Mathematical Puzzles: A Connoisseur's Collection, (A K Peters, 2004), 143, 149-151.