[Opendnssec-develop] Test the new sorter

Rick van Rein rick at openfortress.nl
Wed Jan 27 16:58:01 CET 2010


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


If you want to have the best of both worlds, you'd use IntroSort.


Sorry I didn't mention this before -- I thought everybody knew.


More information about the Opendnssec-develop mailing list