merge - 去戈兰 : Merge Sort Stack Overflow

Question

http://play.golang.org/p/rRccL6YHtQ

我只是实现了与 CLRS 中相同的代码

Pseudocode from CLRS

Merge-Sort(A, p, r)
    if p < r
        q = [(q+r)/2]
        Merge-Sort(A, p, q)
        Merge-Sort(A, q+1, r)
        Merge(A, p, q, r)

Merge(A, p, q, r)
    n_1 = q - p + 1
    n_2 = r - q
    let L[1 .. n_1 + 1]  and R[1 .. n_2 + 1] be new arrays

    for i = 1 to n_1
            L[i] = A[p+i-1]

    for j = 1 to n_2
            R[j] = A[q+j]

    L[n_1 + 1] = INFINITE
    R[n_2 + 1] = INFINITE
    i = 1
    j = 1

    for k = p to r
        if L[i] <= R[j]
                A[k] = L[i]
                i = i + 1
        else A[k] = R[j]
                j = j + 1

但我在合并排序中遇到堆栈溢出。

        [9 -13 4 -2 3 1 -10 21 12]
        runtime: goroutine stack exceeds 250000000-byte limit
        fatal error: stack overflow

        runtime stack:
        runtime.throw(0x1b4980, 0x20280)

我如何使它工作？

        func MergeSort(slice []int, first, last int) {

            if len(slice) < 2 {
                return
            }

            if first < last {
                mid := len(slice) / 2
                MergeSort(slice, first, mid)
                MergeSort(slice, mid+1, last)
                Merge(slice, first, mid, last)
            }
        }

非常感谢!

Answer 1

mid := len(slice) / 2

那不是中间应该去的地方。中间部分应该位于 first 和 last 之间，它们定义了您正在排序的 slice 区域，而不是 slice 的中途。或者，您可以将 slice slice 以生成新 slice 并删除 first 和 last。