归并排序 Merge sort

核心思想是将数据从中间分成前后两个部分，然后对前后两部分分别进行排序，再将排好序的两部分合并在一起。
归并排序使用的是分治思想。

算法步骤

1. 将原始数据平均分成两份，取分割点为mid = len(arr)
2. 使用公式merge_sort(arr) = merge_append(merge_sort(left), merge_sort(right))
3. 其中merge_sort函数的功能是将数组排序，merge_append函数的功能是将两个有序数组合并
4. 设置两个指针，分别为数组其实位置p1和数组中点位置p2
5. 比较两个指针所指的值，较小的值存入最终结果数组中
6. 重复步骤5，直到其中一个指针移动到对应序列的尾端
7. 将另外一个序列的值添加到最终结果数组的尾端。

   动画演示

   

性能分析

• 空间复杂度

任何情况下，归并排序的空间复杂度均为，但是与快排相比，其致命缺点是，归并排序不是原地排序算法。

• 时间复杂度

任何情况下，归并排序的时间复杂度均为。

• 稳定性

是稳定算法

代码实现

func mergeSort(arr []int) []int {
    length := len(arr)
    if length < 2 {
        return arr
    }
    middle := length / 2
    left := arr[0:middle]
    right := arr[middle:]
    return merge(mergeSort(left), mergeSort(right))
}
func merge(left []int, right []int) []int {
    var result []int
    for len(left) != 0 && len(right) != 0 {
        if left[0] <= right[0] {
            result = append(result, left[0])
            left = left[1:]
        } else {
            result = append(result, right[0])
            right = right[1:]
        }
    }
    for len(left) != 0 {
        result = append(result, left[0])
        left = left[1:]
    }
    for len(right) != 0 {
        result = append(result, right[0])
        right = right[1:]
    }
    return result
}