[Sorting] How radixsort can be more useful than quicksort
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
Henrik Sundberg wrote 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.
2007/3/18, Sam Schetterer <samthecppman@gmail.com>:
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
Henrik Sundberg wrote 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. /$
participants (2)
-
Henrik Sundberg -
Sam Schetterer