归并排序

归并排序的基本思想

– 将两个或两个以上的有序序列合并成一个新的有序序列
注意，这里是需要有序序列才能合并！！！！！

要如何实现归并排序呢？

拆分！

– 首先我们要知道，当某个序列只有一个元素的时候，这个序列肯定是有序的，这就是我们的突破口，同时这也
是归并排序递归的出口。
– 将一个无序的序列分成两路，不断重复这个拆分操作，直到所有序列都有序。

合并！

– 多个有序序列合成一个新的有序序列其实很简单，这里以两路为例。记录两路的序列当前元素的坐标为起始位 置，比较两者大小，大的（或者小的）放入辅助空间，然后被放入的那个序列的当前位置后移。
– 当其中一个序列全都放入辅助空间后，剩下的一个序列的元素直接放入辅助空间。
– 当然辅助空间是辅助排序用的，最后还是得把排序好的序列放回原序列。

店小二上代码！！
来嘞

template<typename T>
void Merge(T array[],T helper[],int begin,int mid,int end,bool min2max)
{
    int help_b = begin;
    int left_b = begin;
    int right_b = mid+1;
	//使两路有序序列合成一个有序序列，两个序列可能长度不相同，会导致有部分没有进入辅助空间
    while( (left_b<=mid) && (right_b<=end) )
    {
        if( min2max ? array[left_b]<array[right_b] : array[left_b]>array[right_b] )
        {
//                helper[help_b] = array[left_b];
//                help_b++;
//                left_b++;
            helper[help_b++] = array[left_b++];
        }
        else
        {
//                helper[help_b] = array[right_b];
//                help_b++;
//                right_b++;
            helper[help_b++] = array[right_b++];
        }
    }
    //保证左边的都放入了辅助空间
    while (left_b<=mid)
    {
        helper[help_b++] = array[left_b++];
    }
    //保证右边的都放入了辅助空间
    while (right_b<=end)
    {
        helper[help_b++] = array[right_b++];
    }
    //把辅助空间中的序列放到原数组
    for(int i = begin;i<=end;i++)
    {
        array[i] = helper[i];
    }
}

template<typename T>
void Merge(T array[],T helper[],int begin,int end,bool min2max = true)
{
    if(begin!=end)
    {
        int mid = (begin + end)/2;
        Merge(array,helper,begin,mid,min2max);
        Merge(array,helper,mid+1,end,min2max);
        //真正的归并操作
        Merge(array,helper,begin,mid,end,min2max);
    }
}

template<typename T>
void Merge(T array[],int len,bool min2max = true)
{
    T* help = new T[len];
    Merge(array,help,0,len-1,min2max);
    delete help;
}

归并排序需要额外的辅助空间帮助完成，空间复杂度为 O(n)
归并排序的时间复杂度为 O(n*logn) , 是一种稳定的排序法