It is well-known that sorting permutations by transposition is in $\sf{P}$, as the minimum number of transpositions required to sort $\pi \in S_n$ is exactly $inv(\pi) = \{ (i,j) \in [n] \times [n] : i < j \text{ and } \pi(i) > \pi(j) \}$. This notion of inversion number has also applications in algebraic combinatorics, for instance it allows to endow $S_n$ with a structure of lattice, called the permutohedron and based on the weak Bruhat order.It can be illuminating to recast the problem in group-theoretic terms. We are given a group $G$ with generator set $\Gamma$ and a mapping $i_G : \Gamma^* \rightarrow G$, and another group $H$ on which $G$ acts transitively, and we want to solve the following problem: given $h \in H$, find a minimum-length $w \in \Gamma^*$ such that $i_G(w).h = 1_H$. In the permutation case, $G = H = S_n$ and $\Gamma$ is the set of transpositions.Question: are there other instances of this problem which admit efficient algorithms?
Can we sort without permutations?
sorting