20 Oct
2002
20 Oct
'02
12:29 p.m.
On Sun, 20 Oct 2002 15:08:30 +0300
Eray Ozkural
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