归并排序及优化思路

1.归并排序

void MergrSection(int *a,int *tmp,int begin1,int end1,int begin2,int end2)
{
    assert(a&&tmp);
    int index = begin1;
    while(begin1 <= end1 && begin2 <= end2)
    {
        if(a[begin1] < a[begin2])
        {
            tmp[index++] = a[begin1++];
        }
        else
        {
            tmp[index++] = a[begin2++];
        }
        while(begin1 <= end1)
        {
            tmp[index++] = a[begin1++];
        }
        while(begin2 <= end2)
        {
            tmp[index++] = a[begin2++];
        }
    }
}
void _MergeSort(int *a,int *tmp,int left,int right)
{
    assert(a && tmp);
    if(left < right)
    {
        int mid = left +(right - left)/2;
        _MergeSort(a,tmp,left,mid);
        _MergeSort(a,tmp,mid+1,right);
        MergrSection(a,tmp,left,mid,mid+1,right);
        memcpy(a+left,tmp+left,(right-left+1)*sizeof(int));
    }
}

void MergrSort(int *a,size_t size)
{
    assert(a);
    int *tmp = new int[size];
    _MergeSort(a,tmp,0,size -1);
    delete[] tmp;

}

优化思路：
像快排一样，当区间变小到一定程度时可采用直接插入排序优化其效率。