For applicable data types a good radix sort can beat the pants off comparison sorts by a wide margin but std::sort
is usually implemented as introsort. Is there a reason to not use radix sort to implement std::sort
? Radix sort doesn't fully suffice for implementing std::sort
because std::sort
requires only that types be comparable but for types where comparison and radix based sorting produce the same answer (e.g. int
) this seems like low hanging fruit that's been left unplucked.
Would it be legal to implement std::sort
with overloads that use radix sort when appropriate? Is there something about the requirements of std::sort
that fundamentally prevent this?
Edit: I should have been a tad more clear. I'm asking if it would be legal for an implementation of the standard library to do this. I'm not asking about a user of a standard library implementation placing anything in the std
namespace. I know that doing so is illegal except in specific cases.
The comments quote an "as-if" rule. That's actually not necessary. std::sort
isn't specified "as if introsort is used". The specification for std::sort
is brief and only requires an effect (sorted) and complexity (O(N log N)) for the number of comparisons. Radix sort meets both.
25.4.1.1 sort
template<class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare> void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1 Effects: Sorts the elements in the range [first,last).
2 Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable (17.6.3.2). The type of *first shall satisfy the requirements of MoveConstructible (Table 20) and of MoveAssignable (Table 22).
3 Complexity: O(N log(N )) (where N == last - first) comparisons.
In practice, comparing two register-width values a<b
is a much faster operation than extracting digits and comparing a sequence of those digits, even if we'd use bits or hexadecimal digits. Sure, it's a constant factor difference, but extracting and comparing 32 individual bits is going to be about 100x slower than a direct comparison. That beats most theoretical concerns, especially since log N
can't really be 100 on todays computers.