[m-dev.] Sorting results
Adrian Pellas-Rice
apell at students.cs.mu.oz.au
Thu Feb 8 01:43:46 AEDT 2001
Hi, All.
> 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.
[snip]
> n | sort | fwds bwds rand
> --------+-------+---------------
> 1000 | merge | 200 200 200
> 10000 | merge | 213 157 204
> 100000 | merge | 242 272 294
^^^
A sudden-ish increase from 204 to 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.
At this 3-result stage, the heap and quick sorts seem to be enjoying
logarithmic improvement (relative to list-merge-sort).
On the other hand, the relative improvement of the merge sort would appear
to be better than linear. If put on the spot, I would explain the sudden
improvement for the merge sort as a consequence of the n = 100 000 data
set stressing the L1 cache while the n = 10 000 data set does not (as
much).
I'm too tired/lazy to try analysing it now. However, I would be curious
to hear any additional comments [from anyone], or to know the results if
you [Ralph] happen to try any other values of n.
Adrian Pellas-Rice
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------
More information about the developers
mailing list