# 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 ($\mathbb {Z}$ , $Q$ , $\mathbb {R}$ ...) Let A be a finite subset of that set. Let J be a finite subset of $\mathbb {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)).