I can’t find much reference to this in the literature (see Maus for some hints and an interesting paper) , but surely people have looked at sorting as a problem in group theory? Given a sequence $s=[x_1\dots x_n]$ say a permutation $\pi$ sorts $s$ if and only if $\forall 0 < i < n-1, x_{\pi i} \leq x_{\pi(i+1)}$ — where we could use any partial order. So sorting becomes a problem of finding an element of the permutation group. If $s$ contains no repetitions, if $s_i = s_j$ only when $j=i$ then there is at most one element of $S_n$ that sorts the sequence. If $s$ is a sequence of one value, then every element of $S_n$ sorts the sequence. Maybe $n- |\{x_i: 0 < i \leq n\}|$ tells us how many elements of $S_n$ sort $s$, but perhaps we have to differentiate between repetitions of a single value and repetitions of multiple values.  An element of $S_n, (i,j)$ corresponds to  a swap in $s$ – to

t := s(i); s(i) := s(j); s(j) := t;

so we could describe e.g. quicksort as a sequence of pairs.

Anyone have some references?