mergesort. Reply

[Andrew J Bromage]

G'day all.

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? 

My guess is that a well-written merge sort would probably beat it over
large lists because choosing a random element from a linked list takes
O(N) time.  I'd like to be proven wrong, though, so why don't you
implement it and report back what you find?

> > There is also the heapsort algorithm. Both are fine for *any* data that you 
> > can't do with a bucket/bin sort.

On Sun, Oct 20, 2002 at 01:29:33PM +0100, Duncan Coutts wrote:

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

Over linked lists you wouldn't use a heap, but rather you'd use a
tree-based priority queue.  At this point, my guess is that the cost of
intermediate storage might dominate.

Once again, don't take my word for it.  Try it.

> 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?).

Actually, quick sort can be written to take only O(log N) time to
pull out an element after an initial O(N) cost in setting things up.
This definition will do the trick, assuming that choose_pivot_element
costs no more than O(K) time over a list of length K:

	qsort :: (Ord a) => [a] -> [a]
	qsort xs = qsort' xs []

	qsort' [] = id
	qsort' [x] = (x:)
	qsort' xs
	  = let pivot = choose_pivot_element xs
	    in qsort' (filter (<=pivot) xs) . qsort' (filter(>pivot) xs)

What it boils down to is that both heap sort and quick sort were
designed to sort arrays, so we shouldn't be surprised if they perform
poorly on linked lists.

Cheers,
Andrew Bromage