Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!UKANVAX!MARKV
From: MARKV@UKANVAX ("MARK GOODERUM - UNIV. OF KANSAS ACS - MARKV@UKANVAX")
Newsgroups: comp.lang.modula2
Subject: Re: Sorts
Message-ID: <INFO-M2%89091415014312@UCF1VM>
Date: 14 Sep 89 18:49:00 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: Modula2 List <INFO-M2%UCF1VM.BITNET@PSUVM.PSU.EDU>
Organization: The Internet
Lines: 21

Good points.  Here are some quick notes I looked up last night to add to
this discussion.

Quick sort has a worse case time of O(n^2) but an average case of
O(n log n).  Heapsort is both worst and average case O(n log n) times.
Quicksorts average times are usually a little better than Heapsort.

I should be noted that if often times if you take a set and randomly
distribute the order the elements, then you get a random distribution
that Quicksort can do in n log n quicker than most algorithms.

It should be noted that ANY algorithm for sorting an arbitrary set using
only s LessThan comparison can not be quicker than n log n time.

If something special is known about the keys, like they are all unique,
then times can be improved.  If the keys are all unique and can be reduced
to a contiguous, ordered sequence, then you can sort in O(n) time.

For now,

Mark