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

From: Henrik Sundberg (storangen_at_[hidden])
Date: 2007-03-18 14:39:25

2007/3/18, Sam Schetterer <samthecppman_at_[hidden]>:
> 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.

The '<' is used for branching anyway. Is this really a valid reason?
Constructing concatenated strings for all values to be sorted to be
able to use string sort, seems to be a big overhead.

/$