这是CLRS的2-1.b问题。我不明白如何在n * lg（n / k）中合并大小为k的n / k数组。我能想到的最好的解决方案是通过在每个子列表的min元素中搜索min元素来填充大小为n的最终数组的每个条目。这导致O（nk）。在指定时间内执行此操作的算法是什么？
我刚刚提出了这个问题，我认为答案如下：子列表仍然一次合并两个。 1）考虑合并每个“级别”需要多长时间。 2）考虑有多少合并操作（您开始的第一个列表下面的“级别”数）。
合并每个级别多长时间？每个子列表都有k个元素，因此有（n / k）个子列表。因此，元素的总数是k *（n / k）= n，因此每个级别的合并操作是theta（n）。
有多少合并操作（级别）？
If there is 1 sorted sublist: 0
If there are 2 sorted sublists: 1
If there are 4 sorted sublists: 2
If there are 8 sorted sublists: 3
If there are 16 sorted sublists: 4
1 = 2^0
2 = 2^1
4 = 2^2
8 = 2^3
16 = 2^4
因此，我们可以制定一般规则，格式与上面列出的具体规则相同：
If there are 2^p sorted sublists: p
当我们需要问"2 to the power 'what?' = m"这个问题时，我们需要一个对数。
所以，如果我们问"2 to the power 'what?' = 16?"答案是log to base 2 of 16 = lg 16 = 4
因此，询问有多少级别的合并操作与询问“2权力”是什么一样？ = m“。我们现在知道答案是log to base 2 of n = lg m。
所以我们现在知道有合并操作的lg m级别，并且每个级别的合并操作都需要n时间。因此总时间是n * lg m = n lg m
请记住，m是我们要合并的数字元素，在这种情况下，是算法的插入排序部分返回的已排序子列表的数量。这是n/k。所以，总时间是n log (n/k)。
`我们有n个元素，n / k大小为k的列表（假设链表）。设m = n / k。
1.取一个大小为m的阵列。使用那些n / k列表的第一个元素初始化这些槽。对此数组执行堆排序（time = k log k）。
2.然后提取第一个元素，将其添加到最终列表中。
3.用相应列表中的下一个元素替换第一个元素。如果下一个元素为null，则减小堆大小并将其替换为堆中的最后一个元素。 （时间= O（1））。
4.Do max-heapify（time = O（log k））。重复整个2-3-4过程，直到所有列表都用完为止。
所以，time = 1.heap-sort + 2.max-element 3.Replacement + 4.max-heapify。 = O（k log k）+ O（1）+ O（1）+ n * O（log k）<= O（n log k）。