On 2 Oct , Carsten Kehler Holst wrote:
> Merge Sort vs. Heap Sort (ala Jon)
> As far as I can see the difference between merge sort and heap sort as
> described by Jon is almost non existing.
I'm afraid you need to look a little harder :-)
At first let me note that heapsort as I sent it is flawed in that it
does _more_ comparisons than mergesort for small odd numbers of
elements, so they are not the same!
> mergesort = treefold merge . map runify
you mean treefold merge Nil . map runify
> The main difference is that we call merge recursively instead of
> building a heap node which is later taken apart in flatten_heap.
but the heaps defer some of the comparisons, and group them together
differently.
> I fail to see how Jon's version can be superior and I cannot see
> that points a, b, and c (below) holds (of course (a) can be argued)
I'm afraid I'm not going to give a full explanation here, but the nub
of the matter is as mentioned above.
>>a) When you want to explain the imperative heapsort
>>b) When you know that the data are going to be in an order that is bad for
>> mergesort (take n . concat . repeat) [0,1] for example
Here's a practical comparison (using Hugs 1.3) between your mergesort
as corrected above, and my heapsort as originally sent:
? :gc
Garbage collection recovered 995633 cells
? (length . mergesort . concat . take 5000 . repeat) [0,1]
10000
(769128 reductions, 1260406 cells, 1 garbage collection)
? :gc
Garbage collection recovered 995633 cells
? (length . heapsort . concat . take 5000 . repeat) [0,1]
10000
(388900 reductions, 813056 cells)
and with data designed to make comparisons dominate:
? (length . mergesort . concat . take 5000 . repeat) ["aaaaaaaaaach","aaaaaaaaaagh"]
10000
(5467874 reductions, 10727534 cells, 155 garbage collections)
? (length . heapsort . concat . take 5000 . repeat) ["aaaaaaaaaach","aaaaaaaaaagh"]
10000
(2236721 reductions, 4540208 cells, 67 garbage collections)
?
>>c) when you are worried about the worst-case behaviour more than the average
>> case
As I said originally, mergesort is somewhat faster in the average case.
--
Jon Fairbairn [EMAIL PROTECTED]
18 Kimberley Road [EMAIL PROTECTED]
Cambridge CB4 1HH +44 1223 570179 (pm only, please)
