From: Erik J. Rogers
Subject: Re: Mergesort: why's it efficient?
Date:
Message-ID: <ejrE1twH2.70u@netcom.com>
I know this might belong in another thread (or group for that matter),
but I think here it targets those interested more closely, and it does
relate to the original topic...
* What is a good book/text on such theory (search/sort & other basics)?
I could easily find something suitable, but perhaps there are some that
come with stronger recommendations than others.
Thanks,
Erik J. Rogers
Erik J. Rogers wrote:
>
> I know this might belong in another thread (or group for that matter),
> but I think here it targets those interested more closely, and it does
> relate to the original topic...
>
> * What is a good book/text on such theory (search/sort & other basics)?
> I could easily find something suitable, but perhaps there are some that
> come with stronger recommendations than others.
>
The Bible:
Knuth Vol. 3, Sorting and Searching.
And I know some people don't like it, but I go back to Numerical
Recipes (Press, Flannery, Teukolsky and Vetterling) more often
than to any other collection of algorithms.
--
______________________________________________________________________
David A. G. Gillies (········@vader.brad.ac.uk)
University of Bradford, Bradford, West Yorkshire, England
_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/
David Gillies <········@vader.brad.ac.uk> recommended:
>Knuth Vol. 3, Sorting and Searching.
>Numerical Recipes (Press, Flannery, Teukolsky and Vetterling)
Sedgewick: Algorithms
is quite complete too and has nice illustrations, that's why I prefer
that one.
---
Reini Urban, TU Graz, Architecture & X-RAY
Attention! From: header is garbled on purpose!
<······@sbox.tu-graz.ac.at> http://xarch.tu-graz.ac.at/autocad/
Sorry, I just got in on this discussion, but here's the straight goods.
On average, Quicksort is actually faster than Mergesort, but Mergesort has
a couple of nice features:
Mergesort GUARANTEES O(nlogn) runtime. By the same token, it always
performs all of the steps. Ie. There are no skipped steps or
advantageous cases in most codings of the algorithm. Unless you drop out
of the mergesort at a sufficiently small size of arrays to use an
insertion sort or something else which works well on small problems.
Furthermore Mergesort is a stable algorithm. Ie. It sorts identical
elements and leaves them in their original positions. This is
advantageous in certain conditions. Ie. Imagine a contest for guessing
the number of jelly beans in a jar. If a bunch of people have the correct
answer, you want the prize to go to the first person who submitted his
entry.....You get the picture.
THe main problem is extra space requirements, but its guaranteed runtime
is a big plus!
Keir
--
------------------------------------------------------------------------------
Keir Spilka ········@undergrad.math.uwaterloo.ca
2B CS/EEE Major http://www.undergrad.math.uwaterloo.ca/~knspilka
University of Waterloo
········@undergrad.math.uwaterloo.ca (Keir Spilka) writes:
> On average, Quicksort is actually faster than Mergesort
I made the same claim about 100 years ago in this same thread, and was
gently but immediately given compelling evidence that this is false
for the vast majority of situations.
- Marty
(proclaim '(inline skates))