Lennart wrote
> Well, I'm a sucker for a benchmark so I ran all of these with hbc.
> I also added the smooth merge sort that comes with hbc.
> ...
> As you can see there is no clear winner, but I see no real reason
> to change the sort that comes with hbc to something else at this
> moment.
You are right, I should clarify that the recommendations are ghc
specific (in the next version ;-).
> > sortHbc :: (Ord a) => [a] -> [a]
> > sortHbc [] = []
> > sortHbc (x:xs) = msort (upSeq xs [x])
> >
> > upSeq [] xs = [reverse xs]
> > upSeq (y:ys) xxs@(x:xs) =
> > if x <= y then
> > upSeq ys (y:xxs)
> > else
> > reverse xxs : upSeq ys [y]
> >
> > msort [xs] = xs
> > msort xss = msort (mergePairs xss)
> >
> > mergePairs (xs:ys:xss) = merge xs ys : mergePairs xss
> > mergePairs xss = xss
> >
> > merge xxs@(x:xs) yys@(y:ys) =
> > if x <= y then
> > x:merge xs yys
> > else
> > y:merge xxs ys
> > merge [] yys = yys
> > merge xxs [] = xxs
That's a first-order version of the smooth bottom-up mergesort (which I
did not include in the timings because the difference to the top-down
variant was not significant). `sortHbc' is probably slightly faster
than `smoothMergeSort' because its first-order? NB Bottom-up mergsort
was my previous favourite ;-). Your version has the slight drawback
that it uses only increasing sequences.
> BTW, I don't think the test program does the right thing. It prints
> the last element of the sorted list, but there is nothing that
> says that computing this forces the list to be completely sorted.
> When I test sort routines I always do something like printing the
> sum of the sorted list.
Hmm. I think this does not apply to the examples I gave but you are
right, it could happen.
cheatSort x = [ nth i x | i <- [1 .. length x] ]
where `nth i x' computes the ith smallest element of x.
> Furthermore (while I'm in a whining mode :-), taking the median
> of several runs is not the accepted wisdom. You should take the
> minimum of several runs.
Fixed.
Ralf
