Go Golang：合并排序堆栈溢出

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

I just implement the same code as in 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

But I am getting the stack overflow in the merge sort.

        [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)

How do I make this work?

        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)
            }
        }

thanks a lot!

mid := len(slice) / 2

That's not where the middle should go. The middle is supposed to be halfway between first and last, which define the region of the slice you're sorting, not halfway through the slice. Alternatively, you can slice the slice to make new slices and drop first and last.

You don't seem to be re-slicing the slice you're merge-sorting, so there is no termination of the recursion.

You could either re-slice the slice before recursion, or you can do something like length := last - first (this may have an off-by-one, depending if "last" is the last index or one past the last index) and then go from there.