归并排序法

归并排序法，首先要了解二路归并算法。

所谓二路归并算法，就是指有两个有序队列，设变量i,j,k分别指向有序队列一， 有序队列二，和合并后的有序队列。每次都进行a[i]与b[j]之间的比较，如果a[i]小于b[j],则将a[i]放入到c队列中，然后移动i，直到a[i]大于b[j]。之后b[j]做上面同样的动作，直到a和b队列的所有数据插入完成。

归并排序法的思路是，将一个无序队列，将其在中间分成两部分，依次类推直到初分割的子队列为有序队列（长度为一的元素），然后采用二路归并法，将各个子队列归并为一个有序队列。

算法
void merge(int arr[], int tmparr[], int left, int right, int N)
{
    int llen = right;
    int rlen = N;
    int i=0;
    
    while(left    {
        if(i            tmparr[i++] = arr[left++];
        else
            tmparr[i++] = arr[right++];
    }
   
    while(left < llen) tmparr[i++] = arr[left++];
    while(right < rlen) tmparr[i++] = arr[right++];
   
    for(i=0; N>i; i++)
        arr[i] = tmparr[i];
}


void mergesort(int arr[], int tmparr[], int left, int right)
{
    int mid = (left + right) / 2;
    if(left < right)
    {
        mergesort(arr[], tmparr[], left, mid);
        mergesort(arr[], tmparr[], mid, right);
        merge(arr[], tmparr[], left, mid, right);
    }
}