Go语言实现经典排序算法：归并排序

归并排序是一种高效的排序算法，通过将一个大数组分割成两个较小的子数组，分别对这两个子数组进行排序，然后再将它们合并成一个有序的数组。由于每个子数组在合并时已经是有序的，因此合并过程非常高效。

非递归实现

以下是归并排序的非递归实现代码：

func mergeSort(arr []int) {
    n := len(arr)
    for step := 1; step         for left := 0; left             mid := left + step - 1
            right := min(left+2*step-1, n-1)
            merge(arr, left, mid, right)
        }
    }
}

func merge(arr []int, left, mid, right int) {
    i, j := left, mid+1
    temp := make([]int, 0, right-left+1)
    
    // 合并两个有序子数组
    for i <= mid && j <= right {
        if arr[i] <= arr[j] {
            temp = append(temp, arr[i])
            i++
        } else {
            temp = append(temp, arr[j])
            j++
        }
    }
    
    // 将剩余元素添加到临时数组中
    temp = append(temp, arr[i:mid+1]...)
    temp = append(temp, arr[j:right+1]...)
    
    // 将临时数组中的元素复制回原数组
    copy(arr[left:right+1], temp)
}

func min(a, b int) int {
    if a         return a
    }
    return b
}