归并排序

一、经典归并排序

归并排序就是将要排序的数组分成两部分，每一部分都排好序，再将这两部分归并为一个数组，每一部分的排序又采用归并排序。

归并排序按照空间的使用上来分主要分为两种：普通归并和原地归并。按照归并的方向可以分为自顶向下归并和自底向上归并。

1. merge函数

归并排序最主要的一个函数就是merge，函数接口如下：

void merge(int data[], int start, int mid, int end);

这个函数负责将data数组中start-mid子数组和mid-end子数组进行原地归并，这个函数的前提条件是两个子数组都已经排好序。下面是这个函数的具体实现代码：

//归并两个排好序的数组
void merge(vector<int>& nums, int l, int m, int h)
{
    int i = l, j = m + 1;
    vector<int> aux(nums.begin(), nums.end());
    for (int k = l; k <= h; k++)
    {
        //i>=mid说明前半部分先被合并完，直接将后半部分剩余的元素接到data后面
        if (i > m)
            nums[k] = aux[j++];
        //i>=mid说明后半部分先被合并完，直接将前半部分剩余的元素接到data后面
        else if (j > h)
            nums[k] = aux[i++];
        //两者中选择较小的放到data中
        else if (aux[i] < aux[j])
            nums[k] = aux[i++];
        else
            nums[k] = aux[j++];

    }
}

归并排序最主要的函数就是merge函数，所以保证将merge函数写正确是非常重要的，写归并排序的时候可以先写一个merge函数，然后模拟几个环境测试一下，测试没有问题之后再进行下一步，否则如果一次性将整个归并算法全部写出，出现问题之后，因为递归层数比较多，找起来很麻烦。写好了merge函数，不管是自顶向下还是自底向上归并都只是对merge函数不同方式的调用而已。

2.2 自底向上归并

自底向上：与自顶向下刚好相反，先从子数组依赖树的最低端出发，保证在为一个数组排序时，它的两个部分都已经被排好序，（自顶而下是假设已经排好序，两个不一样）

自底向上代码实现

void merge_sort2(vector<int>& nums)
{
    int size = nums.size();

    for (int sz = 1; sz < size; sz += sz)
    {
        for (int lo = 0; lo < size - sz; lo += sz + sz)
        {
            int end = lo + sz + sz - 1 < size - 1 ? lo + sz + sz - 1 : size - 1;
            merge(nums, lo, lo + sz - 1, end);
        }
    }
}

2. 归并排序的两种方向：

为了直观的理解自顶而下和自底向上，我放了一张图。

性能分析

• 时间复杂度：NlogN
• 空间复杂度：N
• 稳定性：稳定