sorting - HeapSort 与 MergeSort 空间复杂度

Question

当我阅读 CLRS 书中的以下行时，我正在复习我的算法:

Like insertion sort, but unlike merge sort, heap sort sorts in place: only a constant number of array elements are stored outside the input array at any time.

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

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

Answer 1

归并排序确实需要一些工作空间:

在简单的实现中，每个递归调用分配 2 个子数组来复制左右部分，因为它们的元素可能在合并阶段被覆盖。这个工作空间相当于最后一个合并阶段的数据集大小。

在更高级的实现中，单个工作数组在初始阶段分配并传递给递归调用，或在非递归实现的迭代中使用。根据实现细节，这个工作数组的大小可以减少到数据集大小的一半加 1，或者是自底向上迭代实现的下一个 2 的幂。

如果数据元素很大，例如具有多个字段的结构，则有一种替代方法需要更少的工作空间:分配一个指向数据集的指针数组，对该数组进行排序并使用结果数组将原始数据集原地打乱。这可能需要更少的空间，但 shuffle 阶段很棘手。

以上所有都需要一些与成正比的工作空间。否 ，因此空间复杂度为 O(N) ，比插入排序、堆排序、shell排序和快速排序差很多。

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