Value (not position)- based sorting; reference request

Question

A recent answer of Ville Salo on the diameter of a Cayley graph induced by bubble sort generators (adjacent transpositions) has inspired this variation.

Many sort algorithms are position based: you go through a list of pairs of positions in the (integer) array, check the two values, and perform a swap or not. For many simple algorithms (especially in sorting networks) the list of position pairs is fixed, while for less simple algorithms the list may be created based on the input (viz. Quicksort).

The question above uses a limited list of pairs of positions (adjacent transpositions) to investigate. Suppose we use a limited list of values instead?

For the next bit of the post, assume we have scanned an array representing a permutation of the first n positive integers. We can peek all we want, but our swaps are limited to swapping adjacent values: if k and k+1 are both integers in the array, we are allowed to swap them, otherwise keep looking. Thus we never swap the two values 3 and 8 in this scheme, for example.

There may be a duality between indices (position labels) and values that could be exploited to answer questions like the diameter of the analogous graph, but I am not seeing it yet. The first question for me is: does such an exploitable duality exist?

The second and official question for this post is: has the idea of (restricted) value based sorting been explored in the literature? If so, what literature and by what name?

Gerhard "Sorting With A Different Priority" Paseman, 2020.05.08.

Answer 1

An inversion of a permutation $\pi=\pi_1\pi_2\ldots\pi_n$ written in one-line notation is usually defined to be a pair of indices $(i,j)$ with $1 \leq i < j \leq n$ for which $\pi_i > \pi_j$. Inversions are "out-of-order positions." Traditional position-based sorting is about eliminating inversions. But note that the inversions of $\pi^{-1}$ are precisely the pairs $(\pi_{j},\pi_{i})$ for $(i,j)$ an inversion of $\pi$. In other words, these "inverse inversions" are "out-of-order values." So sorting based on values corresponds to eliminating inverse inversions, and has an exactly parallel theory to the usual kind of sorting.

One of these kind of inversions is called "left inversions" and the other "right inversions," but I always get mixed up about which is which. The point is it has to do with whether we are multiplying permutations on the left or right. Indeed, containment of inversion sets gives a partial order on the symmetric group called weak order; the Hasse diagram of weak order is the same as the Cayley graph of the symmetric group with the adjacent transpositions as generators, and the edges of this Hasse diagram correspond as one would expect to multiplying by an adjacent transposition (this graph is also the same as the 1-skeleton of the permutohedron). But there are two kinds of weak orders: left weak order and right weak order, and the distinction is whether we are using left or right inversion sets (equivalently, whether we are multiplying the adjacent transpositions on the left or the right).