# Algorithm Implementation/Sorting/Some proofs

It is impossible to order an unordered set; but sorting usually concerns itself not with sets, but with sequences. Let us define, then, precisely what sequences we may sort, and what the results may entail. Let S be any set with a total ordering (${\displaystyle \mathbb {Z} }$, ${\displaystyle Q}$, ${\displaystyle \mathbb {R} }$...) Let A be a finite subset of that set. Let J be a finite subset of ${\displaystyle \mathbb {N} }$, the natural numbers. Now draw up a function ${\displaystyle \phi :J\rightarrow S}$. The set J induces a so-called permutation group, Sym(J), the set of all bijections from J back onto J. Now let ${\displaystyle \Phi \equiv \{\mu \in Sym)J):\phi \circ \mu }$. A little consideration will convince the reader that the set hereupon described is exactly the set of possible arrangements of the elements of a sequence. Of course, ${\displaystyle \phi _{\mu }=\phi _{\lambda }}$ is possible if it happens that a permutation exchanges indices so that the value of the function doesn't change at the indices; but this will not be a great concern to us. As we will see, exactly one of the functions in ${\displaystyle \Phi }$ is increasing. (A function is increasing whenever x ≥ y implies f(x) ≥ f(y)).