Go语言归并排序实现与栈溢出问题深度解析

func MergeSort(slice []int, first, last int) {
    // 基础情况：如果切片长度小于2，或者first不小于last，则无需排序
    if len(slice) < 2 { // 这行判断可能不准确，因为它检查的是整个slice的长度
        return
    }

    if first < last {
        // 错误的中点计算方式
        mid := len(slice) / 2 

        MergeSort(slice, first, mid)
        MergeSort(slice, mid+1, last)
        Merge(slice, first, mid, last)
    }
}

runtime: goroutine stack exceeds 250000000-byte limit
fatal error: stack overflow

mid := len(slice) / 2

mid := first + (last-first)/2

package main

import (
    "fmt"
    "math" // 用于表示无穷大
)

// MergeSort 对切片中指定范围的元素进行归并排序
func MergeSort(slice []int, first, last int) {
    // 递归终止条件：如果first不小于last，表示子序列只有一个或没有元素，无需排序
    if first < last {
        // 正确计算当前排序范围的中点
        mid := first + (last-first)/2 

        // 递归地对左半部分进行排序
        MergeSort(slice, first, mid)
        // 递归地对右半部分进行排序
        MergeSort(slice, mid+1, last)

        // 合并两个已排序的子序列
        Merge(slice, first, mid, last)
    }
}

// Merge 合并两个有序子序列 A[p..q] 和 A[q+1..r]
func Merge(A []int, p, q, r int) {
    n1 := q - p + 1 // 左子序列的长度
    n2 := r - q     // 右子序列的长度

    // 创建临时切片 L 和 R 来存储左右子序列
    L := make([]int, n1+1)
    R := make([]int, n2+1)

    // 填充 L 切片
    for i := 0; i < n1; i++ {
        L[i] = A[p+i]
    }
    // 填充 R 切片
    for j := 0; j < n2; j++ {
        R[j] = A[q+j+1]
    }

    // 在 L 和 R 的末尾放置哨兵值（无穷大），简化合并逻辑
    L[n1] = math.MaxInt32 // 使用Go语言内置的最大整数值作为哨兵
    R[n2] = math.MaxInt32

    i, j := 0, 0 // L 和 R 的当前索引

    // 合并 L 和 R 到原始切片 A 的指定范围
    for k := p; k <= r; k++ {
        if L[i] <= R[j] {
            A[k] = L[i]
            i++
        } else {
            A[k] = R[j]
            j++
        }
    }
}

func main() {
    arr := []int{9, -13, 4, -2, 3, 1, -10, 21, 12}
    fmt.Println("原始切片:", arr)
    MergeSort(arr, 0, len(arr)-1)
    fmt.Println("排序后切片:", arr) // 期望输出: [-13 -10 -2 1 3 4 9 12 21]

    arr2 := []int{5, 2, 4, 7, 1, 3, 2, 6}
    fmt.Println("原始切片2:", arr2)
    MergeSort(arr2, 0, len(arr2)-1)
    fmt.Println("排序后切片2:", arr2) // 期望输出: [1 2 2 3 4 5 6 7]

    arr3 := []int{1}
    fmt.Println("原始切片3:", arr3)
    MergeSort(arr3, 0, len(arr3)-1)
    fmt.Println("排序后切片3:", arr3) // 期望输出: [1]

    arr4 := []int{}
    fmt.Println("原始切片4:", arr4)
    MergeSort(arr4, 0, len(arr4)-1)
    fmt.Println("排序后切片4:", arr4) // 期望输出: []
}

package main

import (
    "fmt"
)

// MergeSortSlice 对一个切片进行归并排序
func MergeSortSlice(slice []int) []int {
    n := len(slice)
    // 递归终止条件：如果切片长度小于2，则它已经是有序的
    if n < 2 {
        return slice
    }

    // 计算中点
    mid := n / 2

    // 递归地对左右两半部分进行排序
    left := MergeSortSlice(slice[:mid])
    right := MergeSortSlice(slice[mid:])

    // 合并两个已排序的子切片
    return MergeSlices(left, right)
}

// MergeSlices 合并两个有序切片
func MergeSlices(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right)) // 预分配容量

    i, j := 0, 0 // left 和 right 的当前索引

    // 比较并合并元素直到其中一个切片遍历完
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }

    // 将剩余的左切片元素添加到结果中
    for i < len(left) {
        result = append(result, left[i])
        i++
    }

    // 将剩余的右切片元素添加到结果中
    for j < len(right) {
        result = append(result, right[j])
        j++
    }

    return result
}

func main() {
    arr := []int{9, -13, 4, -2, 3, 1, -10, 21, 12}
    fmt.Println("原始切片:", arr)
    sortedArr := MergeSortSlice(arr)
    fmt.Println("排序后切片:", sortedArr)

    arr2 := []int{5, 2, 4, 7, 1, 3, 2, 6}
    fmt.Println("原始切片2:", arr2)
    sortedArr2 := MergeSortSlice(arr2)
    fmt.Println("排序后切片2:", sortedArr2)
}