HeapSort vs MergeSort空间复杂度

Question

当我阅读CLRS书中的以下内容时，我正在研究我的算法：

与插入排序类似，但与合并排序不同，堆排序就地排序：任何时候只有恒定数量的数组元素存储在输入数组之外。

这是否指的是合并排序用于分而治之的左右子列表？

如果是，我们能否以某种方式增强合并排序算法以跳过创建这些子列表？

Answer 1

合并排序确实需要一些工作空间：

• 在朴素实现中，每个递归调用分配2个子数组来复制左右部分，因为它们的元素可能在合并阶段被覆盖。此工作空间相当于上次合并阶段的数据集大小。
• 在更高级的实现中，单个工作数组在初始阶段分配并传递给递归调用，或者在迭代中用于非递归实现。根据实现细节，此工作数组的大小可以减少到数据集大小的一半加1，或者自下而上迭代实现的下一个2的幂。
• 如果数据元素很大，例如具有多个字段的结构，则可以使用另一种方法来减少工作空间：分配指向数据集的指针数组，对此数组进行排序并使用生成的数组将原始数据集随意混合。这可能需要较少的空间，但是洗牌阶段很棘手。

所有这些都需要一些与N成比例的工作空间，因此空间复杂度为O（N），这比插入排序，堆排序，shell排序和快速排序要差得多。

请注意，应用于列表的合并排序不需要O（N）空间，而是需要O（log N）空间，用于自顶向下实现中的递归调用，或者用于迭代自底向上实现的子列表指针数组。然而，在数据结构中已经存在额外的O（N）空间来存储next指针。

Answer 2

通过“在输入数组外部存储恒定数量的数组元素”，它意味着在堆制过程中构建树。它是常数，因为将数据潜入根，左堆和右堆的时间复杂度为O（1）。