Go Golang:合并排序堆栈溢出

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,它们定义了您正在排序的切片区域,而不是切片的中间位置.另外,您也可以切片切片作出新的片拖放first和last.