[boost] [Sorting] How radixsort can be more useful than quicksort

From: Sam Schetterer (samthecppman_at_[hidden])
Date: 2007-03-18 14:08:14

Henrik Sundberg wrote
>Isn't sort within sort handled by a more complex '<' operation?
>I.e '<' returns the order of the inner sort, when the outer is equal.
Henirk, the problem is if one your approach, operator< can become extremely
complex, and therefore, slow. Also, even if there is only one layer of
complexity, checking the outer layer and then possibly checking the inner
layer introduces multiple branches of control into the program, and most of
the time, they will not be followed. Therefore, much of the time that
operator< is called for your complex object, the computers pipeline in
emptied, and for modern computers, that can have a big effect, as their
pipelines can reach sizes of 20 steps, and that takes a long time to refill.
In addition, that approach is still unstable.