MOO-cows Mailing List Archive


RE: sort functions

$list_utils:sort() does an insertion sort, a quadratic algorithm, but
since the insertions are done using the 2-tick listinsert() and
interpretation overhead in MOO is relatively large, you have to get to
fairly big lists (length in the hundreds, as I recall) before you start
losing w.r.t. the more funky methods.

$list_utils:sort_alist() does a merge sort which is tick intensive, but
guaranteed O(nlogn) --- unlike quicksort which is only O(nlogn) on
average.  Adapting :sort_alist() to sort lists (i.e., sort key is
element itself) instead of alists (sort key is element[1]) should be

Another route to an O(nlogn) sort routine is to code up the
insertion-sort using $biglist (list insertion on a $biglist is O(logn)
time --- really what you'd be doing is implementing a tree sort, even
though it'll look like an insertion sort).  This would probably be about
as tick-intensive as :sort_alist.

>From: 	Colin McCormick[]
>Sent: 	Wednesday, September 11, 1996 6:11 AM
>Subject: 	sort functions
>Let's see, I'll try this one more time ...
>Hello folks --
>I'm interested in doing some fast list sorting, using the Quicksort
>algorithm.  $list_utils:sort(), as far as I can tell, is a straight linear
>sort and so doesn't fit my needs. 
>Does anyone have MOO code for a faster sort routine?  Has anyone
>implemented it as a server builtin?  This latter option is the more
>tempting to me, as it'd be easy to take advantage of C's qsort() library
>Colin McCormick
>Tripod, Inc.

Home | Subject Index | Thread Index