归并排序

归并排序思路：就是将数组拆成一个个有序的数组，然后再合并有序数组的过程。

最开始数组中有序数组怎么找到？像插入排序一样，将一个元素看成一个有序的数组，所以,归并就是先将数组分为一个个的元素，再合并起来。

举个例子：4 7 3 2 5 6 1

先递归到最深处

4 7 调用函数Sort将这两个数组合并起来：4 7

3 2 调用函数Sort将这个两个数合并起来：2 3

然后返回上一层将这两个数组 4 7 和 2 3 合并起来　　：2 3 4 7

5 6 调用函数Sort将这个两个数合并起来　：5 6

1 直接返回。

返回上一层将这两个数组 5 6 和 1 合并起来　　　　：1 5 6

返回上一层将 2 3 4 7 和 1 5 6合并起来：1 2 3 4 5 6 7

代码：

void Sort(int* arr,int low,int high)//把两个数组归并起来
{
    int mid = low + (high-low)/2;
    int flag = low;
    int* tmp = (int*)malloc(sizeof(int)*(high-low+1));
    int id = 0;

    int j = mid+1;
    while(low <= mid && j <= high)
    {
        if(arr[low] <= arr[j])
        {
            tmp[id++] = arr[low];
            low++;
        }
        else
        {
            tmp[id++] = arr[j];
            j++;
        }
    }
    while(low <= mid)//前面的还有值
    {
            tmp[id++] = arr[low++];
    }
    while(j <= high)//后面的还有值
    {
            tmp[id++] = arr[j++];
    }
    for(int i = 0;i < high-flag+1;i++)
    {
        arr[flag+i] = tmp[i];
    }

    free (tmp);
    tmp = NULL;
}
void MergeSort(int* arr,int low,int high)
{
    if(arr == NULL || low >= high) return;
    int mid = low+(high-low)/2;
    //先拆分
    MergeSort(arr,low,mid);
    MergeSort(arr,mid+1,high);
    //再合并
    Sort(arr,low,high);
}

多路归并：

void MergeSort(int*arr, int nbegin,int nend,int n)
{
    int* flag = new int[n];
    int length = nend - nbegin+1;
    for(int i = 0; i < n;i++)//每一路的开始下标
        flag[i] = nbegin + length*i/n;
    int* tmp = new int[length];
    int id = 0;
    vector<int> vec;
    for(int i = 0; i < n; i++)
        vec.push_back(arr[flag[i]]);
    int cnt = n;
    while(cnt && vec.size() >= n)
    {
        push_heap(vec.begin(),vec.end(),greater<int>());//小根堆
        tmp[id++] = vec[0];
        for(int i = 0; i < n;i++)
        {
            if(flag[i] == -1)
            {

                continue;
            }
            if(vec[0] == arr[flag[i]])
           {

              pop_heap(vec.begin(),vec.end(),greater<int>());//小根堆
              vec.pop_back();
              flag[i] = flag[i] + 1;
              if(flag[i] <= nbegin + length*(i+1)/n-1)//将标记向下移
              {
                  vec.push_back(arr[flag[i]]);
              }
              else//结束一路
              {
                  flag[i] = -1;
                  cnt--;
              }
                break;
           }
        }
    }
    for(int i = 0; i < vec.size();i++)//根已经放过了
    {
         tmp[id++] = vec[i];
    }

    for(int i =0; i < id;i++ )//放回原数组
        arr[nbegin+i] = tmp[i];
    delete[] tmp;
    delete[] flag;

}