[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