Нижняя граница O (n log n) предназначена для сортировок сравнения , т.е. элементы в массиве можно сравнивать только друг с другом, чтобы проверить, должен ли один быть до или после другого, или если они равны. Это хорошая модель для общих алгоритмов сортировки, потому что она работает практически для любого типа данных, которые вы, возможно, захотите отсортировать; числа, строки, экземпляры пользовательских классов и т. д. Это может быть даже просто тип данных, который можно сопоставить с помощью ключевой функции с некоторыми другими типами данных, поддерживающими сравнения; или вы можете принять функцию компаратора для выполнения сравнений с.
Обратите внимание, что здесь O (n log n) является нижней границей количества сравнений, а не времени выполнения. Если сравнение занимает больше чем O (1) раз, скажем, из-за того, что вы сравниваете длинные строки, которые имеют длинные общие префиксы, тогда время выполнения будет похоже на O (cn log n), где сравнение выполняется в O (c Время Например, сравнение строк длины w в худшем случае занимает время O (w).
Если вам нужен только алгоритм сортировки для данных определенного типа c, то вы можете сделать лучше, потому что другие элементы, указывающие c на этот тип данных, могут быть выполнены над элементами Например, при сортировке целых чисел вы можете использовать элементы массива для индексации другого массива, давая алгоритм counting sort , который выполняется за время O (n + r), где r - диапазон элементов массива.
Если ключи сортировки похожи на строки, в том смысле, что они являются (или могут быть сопоставлены) последовательностями, так что сравнение ключей эквивалентно лексикографическому сравнению этих последовательностей тогда вы действительно можете использовать tr ie для сортировки массива, содержащего этот тип данных. Поздравляем: вы независимо друг от друга заново изобрели алгоритм radix sort , который можно реализовать с помощью попыток . Время его выполнения составляет O (wn), а не O (n), потому что для вставки строки длины w в tr ie требуется время O (w), и вы должны сделать это n раз.
Итак, если элементы не являются строками или «подобны строкам» в вышеприведенном смысле, тогда сортировка по основанию просто не применима. Если элементы являются строками или «строковыми», тогда сортировка по основанию работает, но вместо O (wn log n) требуется время O (wn).
Это означает, что сортировка по основанию не является строго лучше, и вероятно, хуже, когда общие префиксы строк короткие по отношению к самим строкам, что часто имеет место. Для случайных строк обычное сравнение строк занимает в среднем O (1) времени, в этом случае O (n log n) асимптотически лучше, чем сортировка по основанию для строк длиннее, чем O (log n).
В практических приложениях Также следует учитывать скрытые константы в анализе асимптотики c. Сорта сравнения, такие как Timsort , имеют малые скрытые константы, потому что они последовательно обращаются к элементам массива, что приводит к меньшему количеству пропусков кэша по сравнению с обходом дерева, узлы которого не будут последовательными в памяти.