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
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

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
> >