On Tue, Mar 11, 2008 at 5:14 AM, Richard A. O'Keefe <
ok@cs.otago.ac.nz> wrote:
On 11 Mar 2008, at 12:27 pm, Krzysztof Skrzêtnicki wrote:
> I've written little framework to work on. See sortbench.hs and
> sortbench.py attachments.
> Furthermore, I checked Yhc's implementation of sort: it is indeed
> very fast:
I took his earlier code and plugged yhc's sort into it.
Compiling with ghc -O2 using GHC 6.8.2, I found the yhc code (basically
variant of natural merge) to be considerably slower than some of the
alternatives.
(...)
When I run Krzystztof's test harness (which I have currently brought
up to
25 different sorting functions) with a list of the form [1..N] instead
of
a random list, suddenly all the variants of merge sort come out ahead of
all the variants of quick sort. In fact his best version of quicksort,
qsort_iv, comes out fully 1155 times slower than the YHC algorithm on a
list of 10,000 ordered integers. That can be improved by spending a bit
of effort on choosing a good pivot, but then the quicksort algorithms
are
no longer so competitive for randomised inputs.
This paper looks interesting, I'm going to implement those tests.
The classic "Engineering a Quicksort" paper by Bentley and McIlroy from
Software : Practice & Experience recommends a whole bunch of
distribution
shapes (one run, two runs, sawtooth, organ pipes, random, ...) that
should
be benchmarked before drawing too many conclusions.
This is the right point. A further work will be to add different input generators to run them too.
It is also wise to try more than one data type. How do the different
algorithms compare on random samples from a Scrabble dictionary? (Why
that particular question? Because I mean to try it.)