Go Golang：合并排序堆栈溢出

Question

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!

Answer 1

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.