我遇到了这个问题，要求计算算法的最坏情况运行时间，它与mergeSort完全相同，但两个递归调用中的一个被Heapsort代替。
因此，我知道在mergesort中划分需要恒定的时间，并且合并是O（n）。 Heapsort需要O（nlogn）。这就是我想出的：T（n）= 2T（n / 2）+ O（（n / 2）logn）+ O（n）。我对O（（n / 2）logn）部分有些怀疑。是n还是n / 2？我写了n / 2，因为我只在数组的一半上进行了heapsort，但我不确定这是否正确
问题是关于运行时间，但它应该询问时间复杂性吗？
由于提到了递归，这是一个关于自上而下合并排序的问题（而不是自下而上的合并排序）。
使用所描述的代码编写，由于堆排序不是递归的，因此递归仅发生在每个拆分子阵列中的一个上。将调用堆排序来对大小为n / 2，n / 4，n / 8，n / 16，...的子数组进行排序，并且不会发生合并，直到两个大小为1的子数组成为递归分裂。在数组大小为2的幂的简单情况下，“merge sort”仅用于单个元素，其余的子数组大小为{1,2,4,8，...，n / 8，n / 4，n / 2}按堆排序排序然后合并。
由于堆排序比合并排序慢，因此运行时间将更长，但时间复杂度保持为O（n log（n）），因为时间复杂度会忽略常量或更低项因子。
让我们弄清楚在这种情况下复发关系应该是什么。我们在这里
这给了我们这种递归关系：
T（n）= T（n / 2）+ O（n log n）。
为什么这个O（n log n）而不是O（（n / 2）log（n / 2））？原因是大O符号消除了常数因子，因此O（n log n）表示与O（（n / 2）log（n / 2））相同的渐近增长率。为什么T（n / 2）上的系数不是2？这是因为我们只进行一次递归调用;记住，另一个电话被heapsort取代了。
现在剩下要做的就是解决这种情况。它确实对O（n log n）有效，我会留给你决定你想如何展示它。迭代方法在这里是一个很好的选择。