Bubblesort with a twist: a tricky termination

Question

Consider an $n$-tuple $\left(a_1, a_2, \ldots, a_n\right)$ of real numbers. We are allowed to perform the following two moves:

• S-moves: We pick two adjacent entries $a_i$ and $a_{i+1}$ satisfying $a_i > a_{i+1}$ and swap them (i.e., replace them by $a_{i+1}$ and $a_i$, respectively).

• P-moves: We pick two adjacent entries $a_i$ and $a_{i+1}$ satisfying $a_i > a_{i+1}$ and replace them by $a_{i+1}+1$ and $a_i+1$, respectively (i.e., we swap them and then we add $1$ to each of them).

It is well-known ("bubblesort") that if we keep applying S-moves to our $n$-tuple (in succession), then we eventually end up with a weakly increasing $n$-tuple, so that our process terminates. Moreover, it terminates after at most $\dbinom{n}{2}$ many steps, and the exact number of steps it takes to terminate is the number of inversions of $\left(a_1, a_2, \ldots, a_n\right)$ (that is, pairs $\left(i,j\right)$ that satisfy $i < j$ and $a_i > a_j$).

A surprisingly apocryphal result says that

if we keep applying P-moves to our $n$-tuple (instead of S-moves), then the process also terminates after at most $\dbinom{n}{2}$ steps.

It appears logical to look for a similar semiinvariant as the number of inversions for S-moves that would prove this result, but I have not found one for now. Thus the first question:

Question 1. What is a good (more or less explicitly defined) nonnegative integer semiinvariant of an $n$-tuple $\left(a_1, a_2, \ldots, a_n\right)$ that decreases whenever we apply a P-move?

Note that the proof of termination I know (inspired by the solution to Tournament of Towns problem 23/3/6 in Mednikov's and Shapovalov's book) does not use such a semiinvariant; instead it imagines that each entry of our $n$-tuple is drawn on a card (and these cards are swapped along with the respective numbers during an P-move), and then shows that two cards cannot be swapped more than once (the proof is by minimal counterexample, arguing that if two cards get swapped twice, then there must be two other cards that get swapped twice in between these two swaps). It is not a very difficult argument, but rather surprising and somewhat finicky.

P-moves are subtler than they appear at first. Using the diamond lemma and termination, it is not hard to show that they are confluent (i.e., the final result does not depend on the specific moves taken) when the entries $a_1, a_2, \ldots, a_n$ are integers. But they are not confluent in general; a counterexample is the triple $\left(1,1/2,0\right)$, which results in either $\left(1,1,3/2\right)$ or $\left(2,5/2,3\right)$ depending on which path you take.

But there is yet another question that the above definitions lend themselves to asking:

Question 2. If the $n$-tuple $\left(a_1, a_2, \ldots, a_n\right)$ consists of integers, and if we are allowed to make both S-moves and P-moves, then will the process necessarily terminate?

What I know is that it will not terminate if we allow non-integer entries; a simple counterexample is $\left(0,1/3,-1/3\right) \to \left(0,-1/3,1/3\right) \to \left(2/3,1,1/3\right)$ (note that $\left(2/3,1,1/3\right)$ is just the initial triple $\left(0,1/3,-1/3\right)$ with each entry incremented by $2/3$, so that the sequence will go on forever). It is also easy to see that the moves will not be confluent (even for integers). Finally, the number of moves until termination might be larger than $\dbinom{n}{2}$ (for instance, the $6$-tuple $\left(2,1,0,2,0,0\right)$ needs $26$ moves in one of the possible paths).

Answer 1

Question 1:

I don't see any very elegant ones, but here is one that gives something: Let $(a_1, \ldots, a_n)$ be a sequence.

We recursively define that $a_i$ is a barrier for $a_j$ iff $$a_j + \#\{j<k<i|a_k \text{ is not a barrier for } a_j \} \\ \leq a_i + \#\{j<k<i|a_k \text{ is a barrier for } a_j \}$$ Then $\#\{(j<i)|a_i \text{ is not a barrier for } a_j\}$ is strictly decreasing:

When we make a $P$-move interchanging $a_i$ and $a_{i+1}$, generally things that used to be non-barriers may become barriers, but not the other way around: To stop being a barrier, either the number of barriers between $a_k$ and $a_l$ has to decrease or $a_k$ has to increase. After assuming a barrier relation of minimal distance became non-barrier, only the second case can occur, which means it's enough to consider for $a_k$ one of the swapped elements.

For $a_i$ no relations to the right ($a_i \sim a_l, l\ge i+2$) changed. This can be seen by noting that $a_{i+1}$ was not a barrier for $a_i$ before the move, so the left side of the definition did not change ($a_i$ increased by one, but the cardinality went down by one), and neither did the right.

For $a_{i+1}$, no relation to the right ($a_{i+1} \sim a_l, l\ge i+2$) changed either. In this case, both sides of the definition increased by one.

Thus no barrier can become a non-barrier. To see the number of barriers strictly increases, note that $a_{i+1}$ was not a barrier for $a_{i}$ before the move, but $a_i$ is one for $a_{i+1}$ after (For neighbors, barrier is the same as $\ge$).

While not incredibly computable, this invariant does give the optimal $\binom{n}{2}$ bound on runtime, though I do not believe it computes the runtime (as number of inversions does for bubblesort) even for integer sequences.

Question 2: the answer is yes, any such process on integer sequences must terminate:

Let $f(n)$ be the longest runtime possible on a sequence of length $n$. Then $f(1)=0$.

Now, for any series of moves on a vector of length $(n+1)$, the leftmost element needs to be swapped at least every $f(n)+1$ moves. Since the entries are integers, whenever the leftmost entry is swapped either the new entry is smaller than the one before or it is equal, but the entry that used to be there is now one larger (and in position 2). In particular, the number of entries smaller than the leftmost one goes down. This implies the leftmost vector can change at most $n$ times, so $f(n+1)<(n+1)(f(n)+1)<\infty$.