# 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 ($\Z$, $Q$, $\R$...) Let A be a finite subset of that set. Let J be a finite subset of $\N$, the natural numbers. Now draw up a function $\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 $\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, $\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 $\Phi$ is increasing. (A function is increasing whenever x ≥ y implies f(x) ≥ f(y)).