合并排序与基数排序：合并排序在特殊情况下需要 O(n (log n)^2) 时间？
Merge Sort vs Radix Sort : Merge sort taking O(n (log n)^2) time in special cases?
我 reading 关于基数排序与基于比较的排序算法相比的效率，我在那里找到了这篇文章：
For example, consider a bottom-up merge sort. The first pass will compare pairs of random keys, but the last pass will compare keys that are very close in the sorting order. This makes merge sort, on this class of inputs, take O(n (log n)2) time.
谁能帮我理解 O(n (log n)2) 部分？
假设常数比较时间== O(1)，那么归并排序是O(n log(n))。假设比较时间是O(log(n))，那么归并排序是O(N(log(n))^2)。这里的假设基于 n 个不同密钥的最小密钥大小，即 log2(n) 位。但是，密钥大小通常与 n 无关，并且要么是常数，要么是一组 n 个元素中所有密钥的平均大小是常数，在这种情况下，时间复杂度为 O(n log(n)).
要点更多是关于基数排序，其中遍数取决于密钥分成多少部分。例如，如果密钥是 64 位，基数排序一次完成 4 位，则需要 16 遍。如果密钥大小为 28 个字符，基数排序一次完成 1 个字符，则需要 28 遍。如果考虑 n 个不同键的最小键大小，即 log2(n) 位，并且如果一次按 8 位排序，则需要 log256(n) 遍。例如，对 2^32 个键进行排序，意味着键的大小为 32 位，一次按 8 位排序将需要 4 遍。对于 2^64 个密钥，它是每个密钥 64 位和 8 遍。
我 reading 关于基数排序与基于比较的排序算法相比的效率，我在那里找到了这篇文章：
For example, consider a bottom-up merge sort. The first pass will compare pairs of random keys, but the last pass will compare keys that are very close in the sorting order. This makes merge sort, on this class of inputs, take O(n (log n)2) time.
谁能帮我理解 O(n (log n)2) 部分？
假设常数比较时间== O(1)，那么归并排序是O(n log(n))。假设比较时间是O(log(n))，那么归并排序是O(N(log(n))^2)。这里的假设基于 n 个不同密钥的最小密钥大小，即 log2(n) 位。但是，密钥大小通常与 n 无关，并且要么是常数，要么是一组 n 个元素中所有密钥的平均大小是常数，在这种情况下，时间复杂度为 O(n log(n)).
要点更多是关于基数排序，其中遍数取决于密钥分成多少部分。例如，如果密钥是 64 位，基数排序一次完成 4 位，则需要 16 遍。如果密钥大小为 28 个字符，基数排序一次完成 1 个字符，则需要 28 遍。如果考虑 n 个不同键的最小键大小，即 log2(n) 位，并且如果一次按 8 位排序，则需要 log256(n) 遍。例如，对 2^32 个键进行排序，意味着键的大小为 32 位，一次按 8 位排序将需要 4 遍。对于 2^64 个密钥，它是每个密钥 64 位和 8 遍。