归并排序是核心原理是分治和递归的运用，分治，那就需要分而治之，治在这里有治理合并意义。

算法描述

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

实现方式

版本一

func mergeSortV1(arr []int, left, right int) {
    if left >= right {
        return
    }

    mid := left + (right-left)/2     // 1分为2
    mergeSortV1(arr, left, mid)      // 继续分左边
    mergeSortV1(arr, mid+1, right)   //继续分右边
    mergeV1(arr, left, mid+1, right) // 开始合并 mid值为mid+1 右半的起始位置为 mid+1，则 mergeV1 里面的j则从 mid 开始
}

func mergeV1(arr []int, left, mid, right int) {

    tmp := make([]int, right-left+1) // 开辟临时数组

    i, j, k := left, mid, 0

    // 左右两个数组头部元素进行比较，小的插入
    // i 最大值是到不了 mid 的，因为这个 mid 为右半元素的起始位置，而 j可以到 right，right是最右侧元素最后一个位置
    for i < mid && j <= right {
        if arr[i] < arr[j] {
            tmp[k] = arr[i]
            k++
            i++
        } else {
            tmp[k] = arr[j]
            k++
            j++
        }
    }

    // 左边数组剩下元素全部插入
    for i < mid {
        tmp[k] = arr[i]
        k++
        i++
    }

    // 右边数组剩下元素全部插入
    for j <= right {
        tmp[k] = arr[j]
        k++
        j++
    }

    // 临时数组中的元素位置 复制到 arr 中
    for idx, v := range tmp {
        arr[left+idx] = v
    }
}

func TestMergeSortV1(t *testing.T) {
    arr := rand.Perm(10)
    mergeSortV2(arr, 0, len(arr)-1)
    t.Log(arr)
}

版本二

func mergeSortV2(arr []int, left, right int) {
    if left >= right {
        return
    }
    middle := (right + left) / 2
    mergeSortV2(arr, left, middle)
    mergeSortV2(arr, middle+1, right)
    mergeV2(arr, left, middle, right) // 开始合并 mid值为mid 右半的起始位置为 mid+1，则 mergeV2 里面的j则从 mid+1 开始
}

func mergeV2(arr []int, left, middle, right int) {
    temp := make([]int, right-left+1)

    // temp 数组从 0开始
    for i := left; i <= right; i++ {
        temp[i-left] = arr[i]
    }

    // i 是左半数组起点 j是右半数组起点
    i, j := left, middle+1

    // 0,1,2,3,4
    //  left=0 right=4 middle=2 i=0 j=3
    // j-left => 右半数组起始位置 j向右滑动 是在迭代右半数组
    // i-left => 左半数组起始位置 i向右滑动 是在迭代左半数组

    for k := left; k <= right; k++ {
        if i > middle && j <= right {
            // i > middle 其实是左半部分已经全部插入了，现将右半部分插入
            arr[k] = temp[j-left]
            j++
        } else if j > right && i <= middle {
            // j > right 其实是右半部分已经全部插入了，现将左半部分插入
            arr[k] = temp[i-left]
            i++
        } else if temp[i-left] > temp[j-left] {
            // 右半数组插入
            arr[k] = temp[j-left]
            j++
        } else if temp[i-left] <= temp[j-left] {
            // 左半数组插入
            arr[k] = temp[i-left]
            i++
        }
    }
}

小结

归并排序确实还蛮有趣的，很多人看不到分治，其实分治都在参数的调用，和对各自一段切片的处理。

暂时有个想法等排序系列写完，出个 benchmark 让这些排序出来遛一遛，比赛一下