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 an S-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 S-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.

S-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 $1$, 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).

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