Sorting and groups

Image result for permutation groupI 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?

Leave a Reply

Your email address will not be published. Required fields are marked *