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 $latex s=[x_1\dots x_n] $ say a permutation $latex \pi$ sorts $latex s$ if and only if $latex \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 $latex s $ contains no repetitions, if $latex s_i = s_j$ only when $latex j=i$ then there is at most one element of $latex S_n$ that sorts the sequence. If $latex s$ is a sequence of one value, then every element of $latex S_n$ sorts the sequence. Maybe $latex n- |\{x_i: 0 < i \leq n\}|$ tells us how many elements of $latex S_n$ sort $latex s$, but perhaps we have to differentiate between repetitions of a single value and repetitions of multiple values. An element of $latex S_n, (i,j)$ corresponds to a swap in $latex 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?