"Dann Corbit" <DCorbit(at)connx(dot)com> writes:
> Here is a sort template (that can very easily be turned into a C
> routine).
Right offhand I'd guess this to be a loser on not-quite-sorted input,
because the tests it makes to try to prove the input is already sorted
can add significant overhead before failing.
regards, tom lane