[m-dev.] Sorting results

[Thomas Conway]

On Thu, Feb 08, 2001 at 12:47:01AM EST, Ralph Becket wrote:
> n       | sort  | fwds bwds rand
> --------+-------+---------------
> 1000    | merge |  200  200  200
> 10000   | merge |  213  157  204
> 100000  | merge |  242  272  294
	[....]

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

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

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.

Thomas
-- 
  Thomas Conway )O+
 <conway at cs.mu.oz.au>       499 User error! Replace user, and press any key.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------