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. In both normal and radix quicksort, when that is used for branching, the compiler arranges the code so the the cpu will usually follow the right branch path, meaning that it will pipeline into the if or while or for statement. However, in cases like the example, many of the less than statements in the operator< will not be satisfied, breaking the pipeline again and again, especially when it goes all the way to the bottom of the statement. On vault, I have uploaded source code for a radixosrt that shows
Henrik Sundberg wrote the problme with complex operator< (it uses normal radixsort), when compared to the operator[] for normal radixsort. also, imagine that the class that you have designed with a complex operator< is a template class that is used for many types. For radixsort, that size of operator[] is constant. With operator<, it grows to large sizes and causes coad bloat, and it is slow. In addition, even if quicksort is still faster than radixsort, radixsort hs a linear running time (complexity is O(N)), and will always run that fast for any possible order of the data. Finally, going back to the problem of pipelining, radixsort is very pipeline friendy, and almost all of the branches will be properly followed. The only time that will not happen is when each for loop is exited. On computers with long pipelines, like the Pentium Pro, which has a 20 step pipeline, along with many other computers, radixsort will have a huge advantage of quicksort for complex operator<. Then, about creating strings, it is not a very large overhead and only has to be done when the objects change, and is only done on objects containing strings. When strings are normally compared, each byte is examined each time. radix quicksort only examines each byte once, giving it another large advantage over normal quicksort and other non-radix sorts.