[Opendnssec-develop] Test the new sorter

[Rick van Rein]

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.

http://en.wikipedia.org/wiki/Quicksort
http://en.wikipedia.org/wiki/Heapsort

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

http://en.wikipedia.org/wiki/Introsort

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

Cheers,
 -Rick