Merge Sort vs Radix Сортировка: Слияние сортировки O (n (log n)^2) время в особых случаях?

Question

я reading об эффективности Radix сортировки по сравнению с сравнения на основе алгоритмов сортировки, где я нашел этот кусок:

Для примера, рассмотрим снизу вверх сортировки слиянием. Первый проход будет сравнивать пары случайных ключей, но последний проход будет сравнивать ключи, которые очень близки в порядке сортировки. Это делает сортировку слиянием, на этом классе входов, принимает O (n (log n) 2) время.

Может кто-нибудь помочь мне разобраться в части O(n (log n)2)?

Answer 1

Предполагая постоянное время сравнения == O (1), тогда сортировка слияния O (n log (n)). Предполагая, что время сравнения равно O (log (n)), тогда сортировка слияния равна O (N (log (n))^2). Предположение здесь основано на минимальном размере ключа для n различных ключей, которые являются битами log2 (n). Однако размер ключа обычно не зависит от n и является либо постоянным, либо средний размер всех ключей в наборе из n элементов будет постоянным, и в этом случае сложность времени равна O (n log (n)).

Точка, которая делается больше, касается сортировки radix, где количество проходов основано на количестве разделенных ключей. Например, если ключ имеет 64 бита, а сортировка радикса выполняется по 4 бита за раз, это занимает 16 проходов. Если размер ключа составляет 28 символов, а сортировка радикса выполняется по 1 символу за раз, то требуется 28 проходов. Если учитывать минимальный размер ключа для n различных ключей, которые являются битами log2 (n), и если сортировка по 8 бит за раз, то он принимает log256 (n). Например, сортировка 2^32 клавиш означает, что ключи имеют размер 32 бита, а сортировка по 8 бит за раз занимает 4 прохода. Для 2^64 ключей это 64 бит на ключ и 8 проходов.