归并排序(O(n)辅助空间)与原地递归排序(O(1)辅助空间)

归并排序

归并排序是将一个序列划分为同样大小的两个子序列,然后对两个子序列分别进行排序,最后进行合并操作,将两个子序列合成有序的序列.在合成的过程中,一般的实现都需要开辟一块与原序列大小相同的空间,以进行合并操作，所以我们需要最大O(n)的辅助空间用于存储合并序列。下面是归并排序的过程。
归并排序示意图

原地归并排序

原地递归排序的步骤与递归排序一样，都是划分成子序列然后合并子序列，但在实现合并子序列的时候使用了手摇算法实现了序列的合并，可以做到O(1)的辅助空间，但是理论上合并长度为n和m的子序列最坏的复杂度为2*n*m，所以原地归并排序实际意义并不大，但是也可以给我们进行参考。

手摇算法

其实手摇算法的思想很简单，但我口才不好，只能用实际演示给你们看：
假如要将序列1 2 3 4 5的4 5提到1 2 3前面
-> 1 2 3 4 5 原数组
-> 3 2 1 5 4 O(n)的时间将1 2 3翻转，4 5翻转
-> 4 5 1 2 3 O(n)的时间再将数组翻转一次
这时候我们可以看到4 5已经在1 2 3的前面了。我们可以清楚地看到每个数都被交换了2次，所以手摇算法的时间复杂度是2*（n+m）

原地归并算法的实现

我们已经知道了什么是手摇算法，这时候我们可以来演示一下怎么合并两个排好序的序列：
1. 1 3 5 2 4 6 这时的l=0，m=3,r=6,[l,m)是一个序列[m,r)是一个序列,子序列都在list数组里面
2. 1 3 5 2 4 6 比较list[l]和list[m]的大小
3. 当list[l] <= list[m]的时候l++，重复2步骤,当list[l] > list[m]或者l >= m时往下走
4. 1 3 5 2 4 6 这时的l = 1，m = 3,r = 6 再次比较list[l]和list[m]的大小
5. 当list[l] > list[m]的时候m++，重复4步骤并且使用move记录重复次数,当list[l] <= list[m]或者m >= r时往下走
6. 1 3 5 2 4 6 这时的l = 1，m = 4,r = 6
7. 这时候我们可以保证[m-move,m)的序列比list[l]小,所以我么可以使用手摇算法交换[l,m-move)和[m-move,m)的顺序，然后l+=move，因为这时候3的位置在l+move处。
8. 1 2 3 5 4 6 这时候l = 2，m = 4,r = 6，我们重复2步骤继续交换，直到排好顺序。

c++代码实现归并排序和原地归并排序

template<class T>
class MergeSort
{
public:
    enum Type {
        On,O1
        //归并排序的辅助空间复杂度
    };
    void Sort(T *list, int size, Type t = On) {
        if (t == On)MergeOn(list, 0, size);
        else MergeO1(list, 0, size);
    }
private:
    void MergeSortOn(T *list, int l,int m, int r) {//[l,m),[m,r)
        T *a = new T [r - l + 1];
        int index = 0,mid = m,s=l;
        while (l < mid && m < r) {
            if (list[l] < list[m])a[index++] = list[l++];
            else a[index++] = list[m++];
        }
        while (l < mid)a[index++] = list[l++];
        while (m < r)a[index++] = list[m++];
        for (int i = s, j = 0; i < r; i++, j++)list[i] = a[j];
        delete []a;
    }
    void MergeOn(T *list,int l,int r){//[l,r)
        if (l + 1 >= r)return;
        int m = (l + r) / 2;
        MergeOn(list, l, m);
        MergeOn(list, m, r);
        MergeSortOn(list, l, m, r);
    }

    void swap(T& a, T& b) {
        T c = a;
        a = b;
        b = c;
    }
    void reverse(T *list, int l, int r) {//[l,r)
        r--;
        while (l < r)swap(list[l++], list[r--]);
    }
    void hand(T *list, int l, int m, int r) {//手摇算法
        reverse(list, l, m);
        reverse(list, m, r);
        reverse(list, l, r);
    }
    void MergeSortO1(T *list, int l, int m, int r) {
        while (l < m && m < r) {
            while (l < m && list[l] <= list[m]) l++;
            int move = 0;
            while (m < r && list[l] > list[m])move++, m++;
            hand(list, l, m - move, m);
            l += move;
        }
    }
    void MergeO1(T *list, int l,int r) {//[l,r)
        if (l + 1 >= r)return;
        int m = (l + r) / 2;
        MergeO1(list, l, m);
        MergeO1(list, m, r);
        MergeSortO1(list, l, m, r);
    }
};