**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.