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 say a permutation sorts if and only if — where we could use any partial order. So sorting becomes a problem of finding an element of the permutation group. If contains no repetitions, if only when then there is at most one element of that sorts the sequence. If is a sequence of one value, then every element of sorts the sequence. Maybe tells us how many elements of sort , but perhaps we have to differentiate between repetitions of a single value and repetitions of multiple values. An element of corresponds to a swap in – 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?