Было бы законно реализовать перегрузки std::sort с помощью radix sort?

Question

Для применимых типов данных хорошая радикальная сортировка может превзойти сравнительные сортировки с большим отрывом, но std::sort обычно реализуется как интросорт. Есть ли причина не использовать основную сортировку для реализации std::sort? Radix-сортировки недостаточно для реализации std::sort так как std::sort требует, чтобы только типы были сопоставимы, но для типов, где сравнение и сортировка по основанию дают одинаковый ответ (например, int) это похоже на низко висящий фрукт, который остался непорочным.

Было бы законно осуществить std::sort с перегрузками, которые используют радикальную сортировку при необходимости? Есть ли что-то о требованиях std::sort что принципиально этому помешает?

Редактировать: я должен был быть немного яснее. Я спрашиваю, было бы законно для реализации стандартной библиотеки сделать это. Я не спрашиваю о пользователе стандартной реализации библиотеки, помещающей что-либо в std Пространство имен. Я знаю, что это незаконно, за исключением особых случаев.

Answer 1

Комментарии цитируют правило "как будто". Это на самом деле не обязательно. std::sort не указано "как если бы использовался интросорт". Спецификация для std::sort является кратким и требует только эффекта (отсортированного) и сложности (O(N log N)) для количества сравнений. Сорт Radix встречает оба.

25.4.1.1 сортировка

template<class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare> void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

1 Эффекты: сортирует элементы в диапазоне [первый, последний).

2 Требуется: RandomAccessIterator должен удовлетворять требованиям ValueSwappable (17.6.3.2). Тип *first должен удовлетворять требованиям MoveConstructible (Таблица 20) и MoveAssignable (Таблица 22).

3 Сложность: O(N log(N)) (где N == последний - первый) сравнений.

На практике сравнение двух значений ширины регистра a<b это намного более быстрая операция, чем извлечение цифр и сравнение последовательности этих цифр, даже если бы мы использовали биты или шестнадцатеричные цифры. Конечно, это постоянная разность факторов, но выделение и сравнение 32 отдельных битов будет примерно в 100 раз медленнее, чем прямое сравнение. Это превосходит большинство теоретических проблем, особенно с log N не может быть 100 на современных компьютерах.