归并排序

参考资料：
[1]https://blog.csdn.net/yuehailin/article/details/68961304(讲的真好)
[2]http://www.cnblogs.com/skywang12345/p/3602369.html

//归并排序
#include<iostream>

using namespace std;

void merge(int* a,int start,int mid,int end)
{
    int* tmp = new int[end-start+1];//定义1个临时的区域

    int i= start;//第一个有序区索引
    int j = mid+1;//第二个有序区索引
    int k = 0;//临时区域索引

    while(i<=mid && j<=end)
    {

        if(a[i]<=a[j])
            tmp[k++]=a[i++];
        else
            tmp[k++]=a[j++];
    }
    //！！！！如果其中一个有序区空了，那么直接填进行就可以
    while(i<=mid)
    {
        tmp[k++]=a[i++];
    }

    while(j<=end)
    {
        tmp[k++] =a[j++];
    }
    //将排序后的元素，全部整合到a中
    for(i=0;i<k;i++)
    {
        //!!!!!start
        a[start+i]=tmp[i];
    }
    delete[] tmp;
}


void mergeSort(int* a,int start,int end)
{
    if(start >= end)//如果就一个数，那是不行的!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        return;
    //比如 5，7，3，6分为两个序列5，7和6，8
    int mid = (start+end)/2;
    //步骤1：使左边序列变为有序序列
    mergeSort(a,start,mid);
    //步骤2：使右边序列变为有序序列
    mergeSort(a,mid+1,end);

    //步骤3：合并两个有序序列
    merge(a,start,mid,end);
}

int main()
{
    int a[]={40,20,30,10,60,50};
    //数组的长度
    int ilen=sizeof(a)/sizeof(a[0]);
    cout<<"before insert sort"<<endl;
    for(int i=0;i<ilen;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    //查了一下午mergeSort(a,0,ilen)是错的！！！！！！！！！！！！！
    mergeSort(a,0,ilen-1);

    cout<<"after insert sort"<<endl;
    for(int i=0;i<ilen;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}

归并排序的时间复杂度：NlogN