Тема эффективности радикальной сортировки по сравнению с другими алгоритмами сортировки несколько сложна и может вызвать много недоразумений. Является ли сортировка по радиусу одинаково эффективной, менее эффективной или более эффективной, чем лучшие алгоритмы, основанные на сравнении, зависит от деталей сделанных предположений. Эффективность сортировки по радиксу составляет O (d · n) для n ключей, которые имеют d или меньше цифр. Иногда d представляется как константа, что делает радикальную сортировку лучше (для достаточно большого n), чем лучшие алгоритмы сортировки, основанные на сравнении, и все они требуют O (n · log (n)) количества сравнений. Однако в общем случае d нельзя считать константой. В частности, в соответствии с общим (но иногда неявным) предположением, что все ключи различны, тогда d должно быть как минимум порядка log (n), что в лучшем случае (с плотно упакованными ключами) дает временную сложность O (п · журнал (п)) . Казалось бы, радикальная сортировка максимально эффективна по сравнению с сортировками на основе лучшего сравнения (и хуже, если ключи намного длиннее, чем log (n)).
Аргументом счетчика является то, что алгоритмы, основанные на сравнении, измеряются количеством сравнений, а не фактической сложностью времени. При одних допущениях сравнение будет в среднем постоянным, а при других - нет. Сравнение случайно сгенерированных ключей занимает в среднем постоянное время, так как ключи отличаются в первом бите в половине случаев, а во втором бите - в половине оставшейся половины, и т. Д., Что в среднем составляет два бита, которые нужно сравнивать. В алгоритме сортировки первые выполненные сравнения удовлетворяют условию случайности, но по мере сортировки сравниваемые ключи явно больше не выбираются случайным образом. Например, рассмотрим сортировку по принципу «снизу вверх». На первом проходе сравниваются пары случайных ключей, но на последнем проходе сравниваются ключи, которые находятся очень близко в порядке сортировки.
Решающим фактором является распределение ключей. Наилучший случай для сортировки по основанию состоит в том, что они принимаются как последовательные битовые комбинации. Это сделает ключи настолько короткими, насколько они могут быть, все еще предполагая, что они различны. Это делает радикальную сортировку O (n · log (n)), но сортировки, основанные на сравнении, не будут такими эффективными, так как сравнения не будут постоянными по времени в этом предположении. Если вместо этого мы предположим, что ключи представляют собой битовые комбинации длиной k · log (n) для константы k> 1 и базы 2 log, и что они являются равномерно случайными, то радикальная сортировка все равно будет O (n · log (n)). ), но то же самое можно сказать и о сортировках, основанных на сравнении, так как «дополнительная» длина приводит к тому, что даже ключи, которые являются последовательными в отсортированном результате, отличаются настолько, что сравнения в среднем имеют постоянное время. Если ключи длиннее, чем O (log (n)), но случайны, то сортировка по основанию будет хуже. Существует также много других предположений, и большинство из них требуют тщательного изучения, чтобы сделать правильные сравнение.