1B.md

归并排序

插入排序的最大问题在于连续插入带来元素的反复腾挪。归并排序继承了插入排序的基本思想，并克服了这个问题。

归并

　　连续将几个数插入某数列中，结果上等同于把这几个数构成的数列整合到目标数列中。这样多个数列合成一个数列的过程称之为归并。如果参与归并的数列都是有序的，那么在有额外空间的前提下，归并只需一次遍历就可以完成。

func merge[T constraints.Ordered](in1, in2, out []T) {
    i, j, k := 0, 0, 0
    for ; i < len(in1) && j < len(in2); k++ {
        if in1[i] <= in2[j] {
            out[k] = in1[i]; i++
        } else {
            out[k] = in2[j]; j++
        }
    }
    for ; i < len(in1); k++ {
        out[k] = in1[i]; i++
    }
    for ; j < len(in2); k++ {
        out[k] = in2[j]; j++
}   }

分割围歼

　　接下来考虑怎么搞到两个有序子数列。我们可以采用分割围歼的策略：一分二，二分四，当分到足够小的时候，再用插入排序解决。

func mergeSort[T constraints.Ordered](a, b []T) {
    if size = len(a); size < lowerBound {
        InsertSort(a, b)
    } else {
        half := size / 2
        mergeSort(b[:half], a[:half])
        mergeSort(b[half:], a[half:])
        merge(a[:half], a[half:], b)
}   }

优缺点

　　首先应该肯定归并排序的是相当快的，它保持了插入排序比较操作次数为O(NlogN)的优良传统，同时把挪移操作次数也降到了O(NlogN)。其次，对于等值元素对，归并排序不会破坏其固有顺序，这也是一个很好的特性。
　　数组上归并排序的缺点也很突出，就是需要O(N)的额外空间。不过，归并排序只对空间做单向访问，对于容量大而随机访问性能不好的外部存储器而言，归并排序相当合胃口。

---

目录　上一节　下一节