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

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

举个例子：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
     
       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
      
       ());//小根堆        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
       
        ());//小根堆              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;}