Would it be legal to implement overloads of std::sort with radix sort?

Question

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.

Answer 1

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.