I looked at your code and I see that you're using unguarded recursion in quicksort (check Valois's introspective sort >revisited, published in software practice and experience, 2000), swap in insertion sort, int instead of ptrdiff_t (you're >going to have a bad surprise sorting 2 billion integers on a 64bit platform), etc. My experiences showed that radix >sort was not faster than quicksort, due to the random access pattern (for large arrays) and overhead of counters (for >small arrays). And I have some doubts about the endianness (did you test on both big and small endian platforms?). That's a lot of comments. I'll leave it at that. Cheers, Herve Well, Herve, you ask why my radixsort is better than std::sort and std::stable_sort. It is stable, it is faster std::stable_sort, and it's running time is O(kN), where k is the number of bytes in the object. That is
On March 17, Herve Bronimamm wrote >Sam: the Stl already implements sorting (stable and not), inplace and partial sorting (uses heapsort), nth_element >(generalized median), functors and iterators (generic interface). As far as I can tell, your library has no added value, >except you claim performance. I think you might badly underestimate the effort that goes into implementing the >C++ std library. The only reason someone would consider using your library over the standard library would be if >you could convincingly and reproducingly show that you are faster (and by more than a small percentage). I haven't >seen numbers. linear running time, unlike std::sort, which is O(N log N), and radixsort is independent of the input, unlike std::sort. Finally, you can do something called a "sort within sort" using radix quicksort, which is where you sort by one value, than another. These "sort within sorts" are accomplished by appending all of the bytes of your data onto a string, and these bytes come from other strings, integers, and doubles. You then sort it with radix_quicksort, which is incredibly high speed for strings(much faster than std::sort and std::stable_sort). Also, I have uploaded code for radix_sort where you can spcify starting and ending bytes, which is something that I know that the stl does not implement.