Path: utzoo!utgpu!jarvis.csri.toronto.edu!neat.cs.toronto.edu!ephemeral.ai.toronto.edu!bradb
Newsgroups: comp.lang.c
From: bradb@cs.toronto.edu (Brad Brown)
Subject: Re: sorting algorithms
Message-ID: <89Nov9.114339est.2758@neat.cs.toronto.edu>
Organization: Department of Computer Science, University of Toronto
References: <2835@phred.UUCP> <11564@smoke.BRL.MIL>
Date: 9 Nov 89 16:44:21 GMT

gwyn@smoke.BRL.MIL (Doug Gwyn) writes:

>In article <2835@phred.UUCP> stevel@phred.UUCP (Steve Leach) writes:
>>Sorry if this has been discussed befor, but how are the following 
>>sorting methods different?

>The standard answer to such questions about sorting techniques is:
>Read Donald Knuth's "The Art of Computer Programming, Vol. 3 --
>Sorting and Searching".

A more accessable work is Sedgwick's "Algorithms, 2nd ed.".  Knuth is
great if you want to know just about everything there is to know about
an algorithm, but the analysis can get a bit thick and the source
code is hard to read sometimes.  Sedgwick's book is less rigerous,
but the source is in Pascal and the style is much more conversational.

When you start to look at the differences between the algorithms,
look especially at the complexity (roughly the worst case time
it will take to run), the mean complexity, the performance on
partially sorted data (some sorts, like quicksort, can degenerate
badly if you give it partially sorted data), whether you can sort
in-place or on disk, whether you can sort a linked list or an array...

					(-:  Brad Brown  :-)
					bradb@ai.utoronto.ca