Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!atbowler
From: atbowler@watmath.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc,sci.research
Subject: Re: Information on order(N) sort
Message-ID: <5608@watmath.UUCP>
Date: Tue, 3-Mar-87 17:26:50 EST
Article-I.D.: watmath.5608
Posted: Tue Mar  3 17:26:50 1987
Date-Received: Wed, 4-Mar-87 00:38:45 EST
References: <814@fmsrl7.UUCP> <25183@rochester.ARPA> <25329@rochester.ARPA> <2064@cvl.umd.edu>
Reply-To: atbowler@watmath.UUCP (Alan T. Bowler [SDG])
Organization: U. of Waterloo, Ontario
Lines: 39
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:132 comp.lang.misc:315 comp.os.misc:47 sci.research:65

In article <2064@cvl.umd.edu> bhaskar@cvl.umd.edu (S.K. Bhaskar) writes:
>Quicksort requires atleast O(log n) space ; Bubblesort is an in-place sort.
>The extra space needed by Quicksort is the space used by the data structure
>which maintains the subfiles still to be sorted.
>
>Also, Quicksort is O(n log n ) only in the average. The worst case is still
>O(n^2).

While everyone is discussing their favourite sort I might as well remind
the world about Shellsort (as described by Knuth with a relatively prime
delta sequence, not Shell's original binary one).  This has a number of
advantages as the incore sort of first choice.
1) It is an in place sort requiring only constant work space.
2) While its worst case is not well is not well understood, it is
   clearly never as bad as O(n^2).
3) It is simple, and easily implemented.  It requires only a few more
   lines than bubble class sorts.  Quicksort by comparison is easily
   miscoded (witness the famous example in Wirth's book).

I have long conjectured that reason everyone is so fond of Quicksort
is the analysis for the average case behaviour is such a nice example
of the analysis of algorithms.  It is a nice elegant piece of mathematics.
On the other hand, the last I heard, a proper analysis of Shellsort
was still an unsolved problem.  It is clear that its worse case behaviour
is better than O(n^2), but it is equally clear that its best case
is not as good as Quicksort's O(N) and that its average case is not
as good as Quicksort's O(N log N) all that really exists is some empirical
data suggesting things like O(N (log N)^2).

This is not to say that Shellsort is the only choice to make.  It's
simplicity means that it will usually out perform Quicksort on small to
medium problems (the changeover is usually somewhere between 500 and 1000
items), but as the size of the task gets bigger, the fact that it is not
a O(N log N) sort means that other sorts such as Quicksort or Heapsort
will outperform it.  Wheither Quicksort will or not depends on the data.
Heapsort whose behavious is always O(N log N) is guaranteed to outperform
Shellsort for a sufficiently large problem.  However, for a large enough
problem one probably is not doing an in memory sort, and then the classical
merge type sorts tend to be the winners.