Can we sort without permutations? 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 &lt; j \text{ and } \pi(i) &gt; \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?
I don't have a definite answer to your question, but "braid sorting" seems a possible candidate. According to this wikipedia entry we can define it as follows. Let $X$ be a group, and let $H$ denote the set of tuples $(x_1,\ldots,x_n) \in X^n$ such that $x_1 \ldots x_n = 1_X$. If we let $G$ be the braid group $B_n$ generated by the moves $\sigma_i$,  we can define an action of $B_n$ over $H$ by:


  $\sigma_i(x_1,\ldots,x_n) = (x_1,\ldots,x_{i-1},x_{i+1},x_{i+1}^{-1} x_i x_{i+1},\ldots,x_n).$


That is to say, $\sigma_i$ combines the effect of a swap and a conjugation at positions $i$ and $i+1$. It might be possible to solve this problem optimally in polynomial time, which would  answer to your question.