Here is an algorithm that can sort in exactly $d$ steps ($d$ permutations). It uses only the so-called $2$nd subset, where all operations bring the last entry (the $d$) to the front, while allowing you to "shoot" the front entry (the $0$) anywhere.
My key idea is that, the power to move $0$ anywhere makes this similar to how one can sort a hand of cards. I.e. maintain a sorted sub-sequence, and at every step take a new card and insert it into the right place in the sorted sub-sequence, growing the sorted sub-sequence by one card. After inserting $d$ cards you'd be done. It took me a few tries to get all the details right, to map this onto the $2$nd subset.
Here is my first attempt:
Initialization: Color the $2$nd entry (i.e. position $1$ in your numbering scheme) in the input array red. (This step is conceptual - no permutation is actually done.)
Invariant: In between turns, the red entries will always start at the second position (position $1$), be contiguous, and be sorted.
Every turn: Pick the $1$st entry (position $0$), which will be not red. Color it red, and insert it into the existing red sub-array at the right place.
Here is an example: We will sort $FCBDGEA$.
$$
\begin{align}
FCBDGEA & = F\color{red}{C}BDGEA \, \, \, \, \, \, \text{(initialization)}\\
& \rightarrow A\color{red}{CF}BDGE \\
& \rightarrow E\color{red}{ACF}BDG \\
& \rightarrow G\color{red}{ACEF}BD \\
& \rightarrow D\color{red}{ACEFG}B \\
& \rightarrow B\color{red}{ACDEFG} \\
& \rightarrow \color{red}{GABCDEF} \\
\end{align}
$$
Clearly (e.g. by the invariant), after $d$ turns (i.e. $d$ permutations) we end up with the sorted array, but starting at the $2$nd position. I.e., the result is one left-shift from the desired answer. Left-shift is not allowed, but right-shift is in the $2$nd subset, so we can do $d$ more right-shifts and arrive at the desired answer $ABCDEFG$. Therefore this first-attempt runs in $2d$ steps.
My second attempt fixes the "bug" by declaring that the minimum element (here, $A$) be treated as the maximum. Except for this modified sort order, the algorithm is identical to the first attempt. The same example:
$$
\begin{align}
FCBDGEA & = F\color{red}{C}BDGEA \, \, \, \, \, \, \text{(initialization)}\\
& \rightarrow A\color{red}{CF}BDGE \\
& \rightarrow E\color{red}{CFA}BDG \, \, \, \, \, \, \text{(treat $A$ as maximum)}\\
& \rightarrow G\color{red}{CEFA}BD \\
& \rightarrow D\color{red}{CEFGA}B \\
& \rightarrow B\color{red}{CDEFGA} \\
& \rightarrow \color{red}{ABCDEFG} \\
\end{align}
$$
Just like in the first attempt, after $d$ steps (permutations) we end up with the "sorted" array starting at the $2$nd position - except now "sorted" means according to the "modified" sort order, i.e. $BCDEFGA$. Clearly, this means the array starting at the front will be sorted according to the unmodified order. I.e. this second attempt algorithm sorts the array in exactly $d$ steps (permutations), as claimed.
If I understand your $\operatorname{argsort}$ correctly, then $\operatorname{argsort}(x)$ takes as input a finite sequence of distinct numbers -- that is a map from $\{0,1,2,\ldots,n-1\}$ to distrinct numbers -- and produces a permutation $\sigma$ such that $x\circ\sigma$ is an increasing sequence.
Therefore, the fixed points of $\operatorname{argsort}$ are the permutations $\sigma$ where $\sigma\circ\sigma$ is an increasing sequence. But $\sigma\circ\sigma$ is always a permutation, and the only permutation that is increasing is the identity, so the fixed points are the $\sigma$ with $\sigma\circ\sigma=\rm Id$, or in other words permutations of order $1$ or $2$. That is exactly the permutations that are products of disjoint transpositions.
This is relevant because your equation $\operatorname{argsort}(x) = \operatorname{argsort}(\operatorname{argsort}(x))$ calls for $\operatorname{argsort}(x)$ to be a fixed point of $\operatorname{argsort}$.
Thus, the solutions to your equation are exactly the ones that you can make by:
- Start with an increasing sequence.
- Select zero or more non-overlapping pairs of elements in the sequence (not necessarily neighbors), and swap each pair.
Best Answer
Here is a cleaner way to explain it in simple mathematics. Let's denote the original array as $A$, the one after
argsort()once as $A'$, and the final outcome afterargsort()twice as $A''$.Let's first be clear about the following statement: if $A'[i] = j$, then it means $A[j]$ is the i-th smallest element in $A$, by the definition of
argsort(). Then similarly, if $A''[k] = q$, it means $A'[q]$ is the k-th smallest element in $A'$. Recall that, $A'$ actually contains the indices of $A$, therefore, the elements range from $1$ to $|A|$ (allow me to count from $1$ instead of $0$ for the sake of simplicity).!BOOM!: That is to say the k-th smallest element in $A'$ exactly equals to $k$, i.e. $A'[q] = k$. Consequently, by the statement at the beginning, $A[k]$ is the q-th smallest element in $A$, which is saying the rank of $A[k]$ is $q$!
P.S., another more efficient way is to do it this way, to avoid sorting twice.