[m-dev.] Sorting results

[Ralph Becket]

I've been doing some experiments using different sorting algorithms
over arrays and comparing the results against list__sort/1 (a list
based merge sort).

Tests were run on data sets of 1000, 10000 and 100000 elements comprising
of the numbers 1..N in (a) ascending order, (b) descending order and (c)
a random permutation.

The algorithms I tried were
(1) quicksort with median-of-three with an initial randomization pass (*)
(2) heapsort
(3) mergesort

(*) I tried other variants such as (i) insertion-sorting once the subranges
became small and (ii) backing off to heapsort after log(n) partitions, but
neither seemed to work as well as just randomly permuting the input data
before sorting (this does not remove the worst case, but does defer it to
a hopefully very unlikely form).

All tests were compiled using -O6 --intermodule-optimization and
--transitive-intermodule-optimization set.

Here are the results presented as the percentage ratio of list__sort
runtime over array sort runtime averaged over five iterations.

n       | sort  | fwds bwds rand
--------+-------+---------------
1000    | merge |  200  200  200
10000   | merge |  213  157  204
100000  | merge |  242  272  294
--------+-------+---------------
1000    | heap  |   33  100   66
10000   | heap  |   77  114  150
100000  | heap  |  104  165  226
--------+-------+---------------
1000    | quick |   50  100  100
10000   | quick |  106  100  175
100000  | quick |  145  152  255

Mergesort is the clear winner, despite requiring a copy of the input
data as working space.  What amazes me is how well list-based merge
sorting stands up against array based approaches.

I'll post a (hopefully final) diff for array.m using mergesort before
this evening.

One final comment: the texts are quite correct when they suggest that
getting these algorithms right requires a lot of care.

Ralph

--
Ralph Becket      |      MSR Cambridge      |      rbeck at microsoft.com 
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------