<tt><font size=2>Rick van Rein wrote on 01/27/2010 10:58:01 AM:</font></tt>
<br><tt><font size=2><br>
> Hello,<br>
> <br>
> > There is a new sorter available in our SVN. Could you test it
if <br>
> you had any performance issues, e.g. SIDN? Solves some part of the
problem.<br>
> > <br>
> > wget </font></tt><a href=http://trac.opendnssec.org/export/2729/home/bjst/quicksorter.c><tt><font size=2>http://trac.opendnssec.org/export/2729/home/bjst/quicksorter.c</font></tt></a><tt><font size=2><br>
> > gcc -Wall quicksorter.c -o quicksorter<br>
> <br>
> But wait... this relies on QuickSort...?<br>
> <br>
> QuickSort *averages* on O(n.log(n)) complexity, but it can<br>
> be as bad as O(n^2) in bad cases such as sorting an already<br>
> sorted list.  It is more reliable to use HeapSort which always<br>
> has O(n.log(n)) behaviour.</font></tt>
<br>
<br><tt><font size=2>Qsort in stdlib uses median selection to avoid O(n^2).
Heapsort is _slower_ than qsort. Introsort in not in any standard lib.</font></tt>
<br><tt><font size=2> </font></tt>
<br><tt><font size=2>Roy</font></tt>