归并排序

时间复杂度：O(n log n)

• 最好：O(n log n)
• 最坏：O(n log n)

空间复杂度：O(n)

• 需要数据元素大小的额外空间用于交换。

原理
归并排序(Merge Sort)的基本思想是：将两个序列合并在一起，并且使之有序。

该算法是采用分治法（Divide-and-Conquer）的经典的应用。

归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并

实现

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

4. 在 2- 路归并排序算法中，由于需要进行递归调用，为了保证递归的顺利执行，按照一定的方法划分序列，直到子序列成为单个的元素，才开始对相邻的序列进行排序与归并。

   //递归排序
   func MergeSort(slice []int) []int {
    if len(slice) < 2 {
        return slice
    }
    ret := make([]int, 0, len(slice))
    mind := len(slice) / 2
    left := mergeSort(slice[:mind])
    right := mergeSort(slice[mind:])
    for i, j := 0, 0; i < len(left) || j < len(right); {
        if i == len(left) {
            ret = append(ret, right[j:]...)
            break
        }
        if j == len(right) {
            ret = append(ret, left[i:]...)
            break
        }
        if left[i] < right[j] {
            ret = append(ret, left[i])
            i++
        } else {
            ret = append(ret, right[j])
            j++
        }
    }
    return ret
   }