[m-dev.] Sorting results

[Adrian Pellas-Rice]

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
--------------------------------------------------------------------------