[m-dev.] Sorting results

[Ralph Becket]

>From Thomas Conway on 07/02/2001 21:25:00
> 
> Its a shame your table doesn't include another order
> of magnitude or two. Currently, (as alluded to in my
> post to mercury-users yesterday), I'm dealing with
> large lists/arrays which I want to sort at one point,
> and they're in the 10^5 - 10^6 range in size, and they're
> bigger records than ints, so the comparison cost is
> higher (which may be a disadvantage to qsort).

Given that the cost of comparison is a constant factor of the
runtime and that exchanges are still just pointer/word-sized-object
swaps, you should see similar numbers popping out.

> The best thing about mergesort is that although on most data,
> qsort can be coerced into being quicker, mergesort has an upper
> (and average) bound of O(n log n) vs qsort which has an
> upper bound of O(n^2). Ie, mergesort can't go bad on you.

Well, the thing that surprised me (because I bought into the
"qsort is generally quicker" line) was that quicksort didn't 
perform anything like as well as mergesort.  It may be the case
that on a wider spread of random inputs you'd see improvement,
but I'd still be sceptical about its general performance.

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