[Opendnssec-develop] Test the new sorter

[Roy Arends]

Rick van Rein wrote on 01/27/2010 10:58:01 AM:

> Hello,
> 
> > There is a new sorter available in our SVN. Could you test it if 
> you had any performance issues, e.g. SIDN? Solves some part of the 
problem.
> > 
> > wget http://trac.opendnssec.org/export/2729/home/bjst/quicksorter.c
> > gcc -Wall quicksorter.c -o quicksorter
> 
> But wait... this relies on QuickSort...?
> 
> QuickSort *averages* on O(n.log(n)) complexity, but it can
> be as bad as O(n^2) in bad cases such as sorting an already
> sorted list.  It is more reliable to use HeapSort which always
> has O(n.log(n)) behaviour.

Qsort in stdlib uses median selection to avoid O(n^2). Heapsort is 
_slower_ than qsort. Introsort in not in any standard lib.
 
Roy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.opendnssec.org/pipermail/opendnssec-develop/attachments/20100127/c7fe01dd/attachment.htm>