mergesort. Reply

[Duncan Coutts]

On Sun, 20 Oct 2002 15:08:30 +0300
Eray Ozkural <erayo@cs.bilkent.edu.tr> wrote:

> You guys know about the expected running time of randomized quicksort, right? 
> There is also the heapsort algorithm. Both are fine for *any* data that you 
> can't do with a bucket/bin sort.

I've often wondered why the heapsort isn't used for the standard sort
function. 

I heard that one reason hugs used insertion sort was for good lazy
behaviour, you don't have to pay for the whole N^2 sort at once, each
element that is actually requred pays just N.

With heapsort you'd get this behaviour too. You pay N for the first
element (to build the heap) and then log N for each subsequent element.

Quicksort on the other hand is monolithic as is mergsort (right?).

Duncan