From:	Patrick Griffiths <nospam AT po-box DOT mcgill DOT ca>
Newsgroups:	comp.os.msdos.djgpp
Subject:	Re: Sorting Algorythums
Date:	Thu, 05 Mar 1998 20:51:00 -0500
Organization:	McGill University Computing Centre
Lines:	25
Message-ID:	<34FF5684.2772E87C@po-box.mcgill.ca>
References:	<34F113BA DOT 203AD4E9 AT earthlink DOT net> <6cv625$7o6 AT ds2 DOT acs DOT ucalgary DOT ca>
NNTP-Posting-Host:	b54-5.das.mcgill.ca
Mime-Version:	1.0
To:	djgpp AT delorie DOT com
DJ-Gateway:	from newsgroup comp.os.msdos.djgpp

The lower bound on general sorting is O(nlog(n)).
The merge sort algorithm accomplishes this in the worst case,
quick sort in the average case.  Quick sort is O(n^2) in the
worst case.  Radix and Bucket sort are indeed O(n), but like
Paul says, they make assumptions about the data set.

Patrick

Paul Szuch wrote:

> Don't forget Radix or Bucket sorts both are the fastest I know of at
> O(N) but have some special requirements. Radix will only compare
> integers and bucket requires temporary storage.
>
> On Sun, 22 Feb 1998 22:14:18 -0800, "STEVEN S. FALLS"
> <broadview AT earthlink DOT net> wrote:
>
> >    What is the best sorting algorythm and what is it. I mean, how would
> >one program the algrothym?
> >            Thanks,
> >                        -Ardy
> >

- Raw text -