# Interesting problem on sorting

Given a tube with numbered balls (random). The tube has holes to remove a ball. Consider the following steps for one operation:

1. You can pick one or more balls from the holes and remember the order in which you picked the balls.
2. You need to tilt the pipe towards left side so that remaining balls in the pipe shifts towards left and occupy the empty space created by removing the balls.
3. You are not supposed to change the order in which you picked the numbered balls from the pipe. Now you put them back again in the pipe using the vacant space created by movement of balls.

Steps 1 to 3 is considered as one operation.

Find out the minimum operations required to sort the numbered balls in the ascending order.

For example: If tube contains: $[1\ 4\ 2\ 3\ 5\ 6]$

Then we can take out $4$ and $5$ and $6$, and if we tilt pipe to the left, we get $[1\ 2\ 3]$, and we insert $(4\ 5\ 6)$ in that order to the end of pipe to get $[1\ 2\ 3\ 4\ 5\ 6]$.

So minimum number of steps required is 1. I need to find minimum operations to sort the pipe.

Any ideas or hints on how to solve this problem?

-
If they come in the reverse order, you have to take out 2, 3, ... in order and add at the end, for $n$ operations in all. This is clearly the worst case. –  vonbrand Feb 5 '13 at 0:30
8,7,6,5,4,3,2,1 -> 75318642 -> 51627384 -> 12345678 by always taking odd positions out. –  adrianN Feb 5 '13 at 10:17
Summarizing my answer: the minimum number of operations required to sort a permutation $\pi$ is $\lceil \log_2 (d(\pi^{-1})+1) \rceil$, where $d(\cdot)$ is the number of descents. –  Yuval Filmus Feb 5 '13 at 16:52
I like to think of it in terms of removing inversions. With each operation, you can remove inversions between any set $X$ and $S-X$ (where $S$ is the whole set of balls). So, you just have to choose your sets $X$ carefully. –  Joe Feb 6 '13 at 5:43

Define the run-partition number of a permutation $\pi$, denoted $r(\pi)$, using the following process. Let $k$ be the maximal integer such that the numbers $\min(\pi),\ldots,k$ appear in increasing order in $\pi$. Remove them from $\pi$, and repeat the process. The number of rounds it takes to consume the entire permutation is $r(\pi)$.

For example, let's compute $r(62735814)$. We first set aside $1$, to get $6273584$. Then we set aside $234$, to get $6758$. Then we set aside $5$, to get $678$. Finally, we set aside $678$ to get the empty permutation. This takes four rounds, so $r(62735814) = 4$.

How is this representation useful for sorting $62735814$? Take every second run, i.e. $234,678$, and move these numbers to the right to get $51627384$ (edit: in the order they appear in the permutation, i.e. $627384$). Now there are only two runs, namely $1234,5678$, and we can sort the list by moving $5678$ to the right.

Now let me make the following conjecture: For a permutation $\pi$, let $\Pi$ be the set of all permutations that are reachable from $\pi$ within one move. Then $\min_{\alpha \in \Pi} r(\alpha) = \lceil r(\pi)/2 \rceil$.

Given this conjecture, it is easy to show that the minimal number of moves needed to sort a permutation $\pi$ is $\lceil \log_2 r(\pi) \rceil$, and I have verified this formula for all permutations in $S_n$ for $n \leq 8$.

Edit: Here is a different interpretation of the run-partition number which gives a linear time algorithm for computing it, and allows me to sketch a proof of my conjecture, thus verifying the formula $\lceil \log_2 r(\pi) \rceil$.

Consider the permutation $62735814$ again. The reason that the first run ends in $1$ is that $2$ appears before $1$. Similarly, the second run ends in $4$ since $5$ appears before $4$, and so on. Therefore the run-partition number of a permutation is the number of $i$s such that $i+1$ appears before $i$.

We can state this more succinctly if we look at the inverse of the permutation. Consider again $\pi = 62735814$. Take $\pi^{-1} = 72485136$. This permutation has three descents: $7\mathbf{2}48\mathbf{5}\mathbf{1}36$ (a descent is a position smaller than the preceding one). Each of the descents corresponds to the start of a new run. So $r(\pi)$ is equal to one plus the number of descents in $\pi^{-1}$.

What does the operation look like in terms of $\pi^{-1}$? let $B$ be the set of numbers that we move to the right, and $A$ be the set of numbers that stay to the left. We replace the numbers in $A$ with a permutation on $\{1,\ldots,|A|\}$ representing their relative order, and replace the numbers in $B$ with a permutation on $\{|A|+1,\ldots,|A|+|B|\}$. For example, consider the move $\mathbf{6273}5\mathbf{8}1\mathbf{4} \mapsto 51\mathbf{627384}$. In terms of the inverse permutations, it's $7\mathbf{248}5\mathbf{136} \mapsto 2\mathbf{468}1\mathbf{357}$. So $75$ was mapped to $21$ and $248136$ was mapped to $468357$.

A descent $\ldots xy \ldots$ in $\pi^{-1}$ is lost after the operation only if $x \in A$ and $y \in B$. Conversely, in terms of $\pi^{-1}$, the partition into $A$ and $B$ corresponds to $A$-runs and $B$-runs; every time a $B$-run ends and an $A$-run begins, there is a descent. In order to "kill" a descent, we have to switch from an $A$-run to a $B$-run. If we kill two descents, we will have switched in the middle from a $B$-run to an $A$-run, incurring a descent.

This argument can be formalized to show that if $\alpha$ arises from $\pi$ via an operation, then $d(\alpha^{-1}) \geq \lfloor d(\pi^{-1})/2 \rfloor$, where $d(\cdot)$ is the number of descents. This is equivalent to $r(\alpha) \geq \lceil r(\pi)/2 \rceil$, thus proving one direction of my conjecture. The other direction is easier, and was already outlined above: we simply take every second run and push these runs to the right to get a permutation $\alpha$ satisfying $r(\alpha) = \lceil r(\pi/2) \rceil$.

-
You are taking out several rounds of balls at once, I understand that isn't allowed. –  vonbrand Feb 4 '13 at 23:20
I'm taking them in the order they appear in the permutation. That is legal. –  Yuval Filmus Feb 5 '13 at 0:14
i am bit confused. can you please explain min number of operations required to sort [6 5 4 3 2 1] and also you mentioned like "Take every second run, i.e. 234,678, and move these numbers to the right to get 51627384" can you please explian this with detail and also how to calculate r(π) efficently? –  user6709 Feb 5 '13 at 5:17
1) $r(654321) = 6$, so you would need 3 operations. For example, $654321 \to 531|642 \to 51|6234 \to 1234|56$. –  Yuval Filmus Feb 5 '13 at 6:31
2) You take all the numbers belonging to these runs (in the order they appear in the permutation), and move them to the right. In this case, you take $627384$ and move them to the right, leaving $51$ to the left. –  Yuval Filmus Feb 5 '13 at 6:32