Re: No merge sort?

> -----Original Message-----
> From: Jason M. Felice [mailto:jfelice@cronosys.com]
> Sent: Monday, April 07, 2003 1:10 PM
> To: pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] No merge sort?
>
>
> On Mon, Apr 07, 2003 at 03:36:10PM -0400, Greg Stark wrote:
> > "Ron Peacetree" <rjpeace@earthlink.net> writes:
> >
> > > AFAIK, there are only 3 general purpose internal sorting
> techniques
> > > that have O(n) behavior:
> >
> > Strictly speaking there are no sorting algorithms that have
> worst-case
> > time behaviour better than O(nlog(n)). Period.
> >
>
> Not true.
>
http://www.elsewhere.org/jargon/html/entry/bogo-sort.html

He said "better than" not "worse than".

For comparison based sorting it is _provably_ true that you cannot sort
faster than log(n!) which is O(n*(log(n))).