为什么递归合并排序优于迭代合并排序，即使后者具有辅助 space 复杂性？

Question

在研究合并排序算法时，我很好奇这种排序算法是否可以进一步优化。发现存在具有相同时间复杂度但更好 O(1) space 复杂度的合并排序算法的迭代版本。就性能而言，迭代方法总是优于递归方法。那为什么它在任何常规算法课程中都不那么常见并且很少被谈论呢？ Here's the link to Iterative Merge Sort algorithm

Answer 1

Found out that there exists Iterative version of Merge Sort algorithm with same time complexity but even better O(1) space complexity

您链接到的合并排序的迭代 bottom-up 实现没有 O(1) space 复杂性。它维护数组的副本，因此这表示 O(n) space 复杂度。因此，这使得额外的 O(logn) 堆栈 space （对于递归实现）与总的 space 复杂度无关。

在您的问题标题和一些评论中，您使用了 “辅助 space 复杂性” 等词。这就是我们通常所说的 space 复杂性，但您似乎暗示这个术语意味着 constant space 复杂性。这不是真的。 “辅助”是指输入所用的space以外的space。这个术语没有告诉我们实际的复杂性。

Answer 2

如果您认为它具有 O(1) space 的复杂性，请再看一遍。它们具有大小为 n 的原始数组 A，以及大小为 n 的辅助数组 temp。（实际上只需要 n/2 但他们保持简单。）

他们需要第二个数组的原因是当你合并时，你将底部区域复制到临时区域，然后从它原来的位置开始合并回来。

所以权衡就是这样。递归解决方案涉及的繁琐位更少，概念更清晰，但在两个解决方案共享的 O(n) 内存开销之上增加了 O(log(n)) 内存开销。当您尝试交流概念时，这是一个直接的胜利。

此外，在实践中我相信递归也是一种胜利。

在迭代方法中，您不断地遍历整个数组。在大型数组的情况下，这意味着数据进入缓存进行一次传递，被操作，然后在您加载数组的其余部分时丢失。只需要在下一次通过时再次加载。

相比之下，在递归方法中，对于相当于前几遍的操作，您将它们加载到缓存中，对它们进行完全排序，然后继续。（你赢得多少次胜利在很大程度上取决于数据类型、内存布局和 CPU 缓存的大小。）当你将太多数据合并到适合缓存。算法课程通常会忽略此类底层细节，但它们对实际性能非常重要。

Answer 3

递归自顶向下合并排序主要是教育性的。大多数实际的库使用混合插入排序和自下而上合并排序的一些变体，使用插入排序创建小的排序运行s ，这些运行s 将在偶数次合并传递中合并，以便在原始之间来回合并临时数组以原始数组中的排序数据结束（除了数组末尾的单例运行s 之外，合并中没有复制操作，这可以通过选择适当的初始运行大小来避免对于插入排序（注意 - 这在我的示例代码中没有完成，我只使用运行大小 32 或 64，而像 Timsort 这样的更高级的方法确实选择了合适的运行大小）。

自下而上稍微快一些，因为数组指针和索引将保存在寄存器中（假设优化编译器），而自上而下是将数组指针和索引推入|从堆栈中弹出。

虽然我不确定 OP 实际上意味着合并排序的 O(1) space 复杂度，但它是可能的，但它比传统的 O(n) 合并排序慢了大约 50% )辅助space。现在主要是研究（教育）工作。代码相当复杂。 Link 到示例代码。其中一个选项是根本没有额外的缓冲区。基准 table 适用于相对较少的键（最多 32767 个键）。对于大量的键，这个例子最终比优化插入+自下而上的归并排序慢了大约 50%（std::stable_sort 被泛化了，比如每次比较都使用指向函数的指针，所以它是未完全优化）。

https://github.com/Mrrl/GrailSort

示例混合插入 + 自底向上合并排序 C++ 代码（省略原型）：

void MergeSort(int a[], size_t n)           // entry function
{
    if(n < 2)                               // if size < 2 return
        return;
    int *b = new int[n];
    MergeSort(a, b, n);
    delete[] b;
}

void MergeSort(int a[], int b[], size_t n)
{
size_t s;                                   // run size 
    s = ((GetPassCount(n) & 1) != 0) ? 32 : 64;
    {                                       // insertion sort
        size_t l, r;
        size_t i, j;
        int t;
        for (l = 0; l < n; l = r) {
            r = l + s;
            if (r > n)r = n;
            l--;
            for (j = l + 2; j < r; j++) {
                t = a[j];
                i = j-1;
                while(i != l && a[i] > t){
                    a[i+1] = a[i];
                    i--;
                }
                a[i+1] = t;
            }
        }
    }

    while(s < n){                           // while not done
        size_t ee = 0;                      // reset end index
        size_t ll;
        size_t rr;
        while(ee < n){                      // merge pairs of runs
            ll = ee;                        // ll = start of left  run
            rr = ll+s;                      // rr = start of right run
            if(rr >= n){                    // if only left run
                rr = n;                     //   copy left run
                while(ll < rr){
                    b[ll] = a[ll];
                    ll++;
                }
                break;                      //   end of pass
            }
            ee = rr+s;                      // ee = end of right run
            if(ee > n)
                ee = n;
            Merge(a, b, ll, rr, ee);
        }
        std::swap(a, b);                    // swap a and b
        s <<= 1;                            // double the run size
    }
}

void Merge(int a[], int b[], size_t ll, size_t rr, size_t ee)
{
    size_t o = ll;                          // b[]       index
    size_t l = ll;                          // a[] left  index
    size_t r = rr;                          // a[] right index
    while(1){                               // merge data
        if(a[l] <= a[r]){                   // if a[l] <= a[r]
            b[o++] = a[l++];                //   copy a[l]
            if(l < rr)                      //   if not end of left run
                continue;                   //     continue (back to while)
            while(r < ee)                   //   else copy rest of right run
                b[o++] = a[r++];
            break;                          //     and return
        } else {                            // else a[l] > a[r]
            b[o++] = a[r++];                //   copy a[r]
            if(r < ee)                      //   if not end of right run
                continue;                   //     continue (back to while)
            while(l < rr)                   //   else copy rest of left run
                b[o++] = a[l++];
            break;                          //     and return
        }
    }
}

size_t GetPassCount(size_t n)               // return # passes
{
    size_t i = 0;
    for(size_t s = 1; s < n; s <<= 1)
        i += 1;
    return(i);
}

为什么递归合并排序优于迭代合并排序，即使后者具有辅助 space 复杂性？

Why is recursive Merge Sort preferred over iterative Merge Sort even though the latter has auxillary space complexity?

sorting

algorithm

recursion

mergesort