合并排序导致堆栈溢出？

Question

我用 C++ 为链表编写了 mergesort()。问题是我的教授提供了一个非常大的列表（长度为 575,000）的测试代码。这会导致我的函数发生堆栈溢出错误，因为它是递归编写的。

所以我的教授可能希望我们使用迭代而不是递归来编写它。我想问下是不是我的代码有什么问题导致栈溢出？

我的代码：

typedef struct listnode {
    struct listnode * next;
    long value; 
} LNode;

LNode* mergesort(LNode* data) {
    if(data == NULL || data->next == NULL) {
        return data;
    }else {
        LNode* s = split(data);

        LNode* firstSortedHalf = mergesort(data);
        LNode* secondSortedHalf = mergesort(s);

        LNode* r = merge(firstSortedHalf, secondSortedHalf);
        return r;
    }
}

LNode* split(LNode* list) {
    if(list) {
        LNode* out = list->next;

        if(out) {
            list->next = out->next;
            out->next = split(out->next);
        }
        return out;
    }else {
        return NULL;
    }
}

LNode* merge(LNode* a, LNode* b) {
    if(a == NULL)
        return b;
    else if(b == NULL)
        return a;

    if(a->value < b->value) {
        a->next = merge(a->next,b);
        return a;
    }else {
        b->next = merge(a, b->next);
        return b;
    }
}

Answer 1

所以你有三个递归函数。让我们看看每个元素的最大深度，最坏情况是 575000 个元素的列表：

merge(): 这看起来遍历整个列表。所以 575000 个堆栈帧。
split(): 这看起来是成对地遍历整个列表。所以 ~250000 个堆栈帧。
mergesort(): 这看起来以分裂的方式迭代。所以 log_2(575000) 或大约 20 个堆栈帧。

因此，当我们运行我们的程序时，我们会获得有限数量的堆栈 space 以适应我们所有的堆栈帧。在我的电脑上，默认限制约为 10 兆字节。

粗略估计每个堆栈帧占用 32 个字节。对于 merge() 的情况，这意味着它将占用大约 18 兆字节的 space，这远远超出了我们的限制。

mergesort() 调用自身，但只有 20 次迭代。这应该符合任何合理的限制。

因此，我的结论是 merge() 和 split() 不应以递归方式实现（除非该方式是尾递归且已启用优化）。

Answer 2

有点晚了，但它是导致堆栈溢出的递归 merge()。递归 split() 不是问题，因为它的最大深度是 log2(n).

所以只需要将merge()转为迭代

正如很久以前评论的那样，使用一个小的（25 到 32 个）指针数组的自下而上的方法更简单、更快速，但我不确定如果获得太多帮助，这会是一个问题分配。 Link 到 wiki 伪代码：

http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

Link 工作 C 示例：

http://code.geeksforgeeks.org/Mcr1Bf

合并排序导致堆栈溢出？

Merge sort causing stack to overflow?

c++

stack-overflow

mergesort

linked-list