归并排序

《算法（第4版）》笔记

归并

归并排序基于“归并”这个简单的操作，即将两个有序的数组归并成一个更大的有序数组。

要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。

// c++
template<class T>
void merge(T& a, int lo, int mid, int hi, T& aux)
{
    // 将a[lo .. mid]和a[mid+1 .. hi]归并
    int i = lo;
    int j = mid + 1;

    for (int k=lo; k<=hi; ++k)
        aux[k] = a[k];

    for (int k=lo; k<=hi; ++k)
    {
        if (i > mid)
            a[k] = aux[j++];
        else if (j > hi)
            a[k] = aux[i++];
        else if (aux[j] < aux[i])
            a[k] = aux[j++];
        else
            a[k] = aux[i++];
    }
}

# python
def merge(a, lo, mid, hi, aux):
    # 将a[lo .. mid]和a[mid+1 .. hi]归并
    i = lo
    j = mid + 1

    for k in range(lo, hi + 1):
        aux[k] = a[k]

    for k in range(lo, hi + 1):
        if i > mid:
            a[k] = aux[j]
            j += 1
        elif j > hi:
            a[k] = aux[i]
            i += 1
        elif aux[j] < aux[i]:
            a[k] = aux[j]
            j += 1
        else:
            a[k] = aux[i]
            i += 1

自顶向下的归并排序（递归）

// c++
template<class T>
void merge_sort(T& a, int lo, int hi, T& aux)
{
    if (hi <= lo)
        return;

    int mid = lo + (hi - lo) / 2;
    merge_sort(a, lo, mid, aux);      // 将左半边排序
    merge_sort(a, mid + 1, hi, aux);  // 将右半边排序
    merge(a, lo, mid, hi, aux); // 归并结果
}

// 将容器a按升序排列
template<class T>
void merge_sort(T& a)
{
    T aux;
    aux.resize(a.size());
    merge_sort(a, 0, a.size() - 1, aux);
}

# python
def merge_sort_p(a, lo, hi, aux):
    if hi <= lo:
        return

    mid = lo + (hi - lo) // 2
    merge_sort_p(a, lo, mid, aux)
    merge_sort_p(a, mid + 1, hi, aux)
    merge(a, lo, mid, hi, aux)

# 将列表a按升序排列
def merge_sort(a):
    aux = [None] * len(a)
    merge_sort_p(a, 0, len(a) - 1, aux)

归并排序所需的时间和NlogN成正比。

可以用归并排序处理数百万甚至更大规模的数组，这是插入排序或者选择排序做不到的。归并排序的主要缺点是辅助数组所使用的额外空间和N的大小成正比。

通过一些细致的思考我们还能够大幅度缩短归并排序的运行时间，比如对小规模子数组使用插入排序。使用插入排序处理小规模的子数组（比如长度小于15）一般可以将归并排序的运行时间缩短10%~15%。

自底向上的归并排序

实现归并排序的另一种方法是先归并那些微型数组，然后再成对归并得到的子数组，如此这般，直到我们将整个数组归并在一起。这种实现方法比标准递归方法所需要的代码量更少。首先我们进行两两归并（把每个元素想象成一个大小为1的数组），然后是四四归并（将两个大小为2的数组归并成一个有4个元素的数组），然后是八八归并，一直下去。

// c++
// 将容器a按升序排列
template<class T>
void mergeBU_sort(T& a)
{
    int n = a.size();

    T aux;
    aux.resize(n);

    for (int sz = 1; sz < n; sz += sz)
        for (int lo = 0; lo < n - sz; lo += sz + sz)
            merge(a, lo, lo + sz - 1, std::min(lo + sz + sz - 1, n - 1), aux);
}

# python
# 将列表a按升序排列
def mergeBU_sort(a)
    n = len(a)
    aux = [None] * n

    sz = 1
    while sz < n:
        for lo in range(0, n - sz, sz + sz):
            merge(a, lo, lo + sz -1, min(lo + sz + sz - 1, n - 1), aux)
        sz += sz