The test is O(n)
> -----Original Message-----
> From: Tom Lane [mailto:tgl@sss.pgh.pa.us]
> Sent: Tuesday, December 13, 2005 10:51 AM
> To: Dann Corbit
> Cc: Qingqing Zhou; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql-
> hackers@postgresql.org
> Subject: Re: [HACKERS] Which qsort is used
>
> "Dann Corbit" <DCorbit@connx.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