Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!cmcl2!brl-adm!adm!bard@THEORY.LCS.MIT.EDU
From: bard@THEORY.LCS.MIT.EDU (Bard Bloom)
Newsgroups: comp.lang.c
Subject: sorting (qsort)
Message-ID: <10491@brl-adm.ARPA>
Date: Sat, 21-Nov-87 16:16:57 EST
Article-I.D.: brl-adm.10491
Posted: Sat Nov 21 16:16:57 1987
Date-Received: Mon, 23-Nov-87 04:44:48 EST
Sender: news@brl-adm.ARPA
Lines: 84



> My question is: do these people know something about quicksort
> that I don't?  Contrast merge sort and quicksort:

Quicksort -- if you code it just right -- has a very nice inner loop:

   v := a[r]
   i := left-1; j := right;
   REPEAT
     REPEAT i := i+1 UNTIL a[i] >= v;
     REPEAT j := j-1 UNTIL a[j] <= v;
     a[i] :=: a[j]
   UNTIL j <= i;

Notice that most of the work is simply an increment and a comparison of an
indexed variable against a fixed value v.  Most other sorting algorithms have
a lot more bookkeeping --- diddling two indices doubles the amount of work
--- and have comparisons a[i]<=a[j] which involve indexing twice.  Of course,
you typically have to code this in assembly language or something to get the
most out of it; if you have (e.g.) a subroutine call to compare strings, you
lose a large chunk of the speedup.

Here's the verdict on Quicksort (from Sedgwick's _Algorithms_).  He does not
justify all these points, so check the literature rather than flaming at me.
Try Aho, Hopcroft, and Ullman for the references.

It's been around a long time, and is very well understood.  It works well in
a variety of situations, and consumes less resources than any other sorting
method in many situations.  The analysis has been verified by extensive
empirical experience.  A carefully tuned version of Quicksort is likely to
run significantly faster than any other sorting method on most computers.  
The carefully tuned version uses a number of tricks, e.g. switches to another
sorting algorithm (e.g., full decision tree) when the lists get too short.
Often parts are coded in assembly language.

However, Quicksort is very very delicate; if you don't implement it just
right, it slows down a lot.  To make matters worse, usually if you screw up
the quicksort, it still stays a correct sorting algorithm.  It is so touchy
that you should use some simpler algorithm -- shellsort is a good one --
unless you really want to take the time to get your quicksort perfect.  I
don't know what version you were using; was it a carefully tuned version, or
a naive implementation?  (The simplest implementation is O(N^2) on a sorted
list; a smarter one is O(N).)

> (2')	merge sort can be coded to take o(N) comparisons when
>	the input is already in order.



>   (1')	merge sort does o(NlgN) comparisons in the WORST case.
                                ^^^^^^^
>   (1")	quick sort does o(1.4NlgN) comparisons on the AVERAGE.
>       	In the worst case it does O(N**2) comparisons.


(Comment on the mathematics: You presumably mean O(NlgN).  o(NlgN) means
"asymptotically less than NlgN", which is impossible for any comparison
sorting algorithm.  O(1.4NlgN) is precisely the same thing as O(NlgN); the O
operator ignores constant factors.  Check any Intro Algorithms book on this
point; it's important if you want to analyse algorithms.)

Most people don't worry about the constant factors, because they vary a lot
with the model of computation.  Most likely your source just said O(NlgN)
time for Mergesort, meaning kNlgN for some value of k which depends on fine
points of your computer architecture.  The same comments go for Quicksort.
Unless you've done some fine analysis, 1" isn't saying much.

> Have C implementors been hypnotised by the magic word "quick" in
> the name of "quick" sort, or am I missing something?  30% overhead
> seems a lot to pay just for a name.

No.  They may have been hypnotized by the 27 years of practical and
theoretical investigation of how quicksort works and how to make it work
well.  They may have seen papers that said "Quicksort is the best" and then
gone out and implemented a decent-enough quicksort, without making sure that
they were tweaking it in just the right way to make it the best.  

Since the people who wrote it for your SunOs presumably had to write their
own code from scratch, they might not have taken the time to search the
(unsorted and fairly hairy) literature to get the fine points right.  If you
can find a machine which has a carefully tweaked qsort, try your comparison there.

-- Bard