/*
    时间：2021年12月20日00:03:43
    内容：归并排序算法模板
    心得:  归并排序一定要理解归并的过程，以及递归的过程！ 
*/ 
 
void merge_sort(int q[], int l, int r)  // 给定数组，左边界，右边界 
{
    if(l >= r) return;    // 如果数组只有一个数或者没有数，则 不需要再进行下面的操作，直接退出 
    int mid = l + r >> 1;  // 找到中点 
    merge_sort(q, l, mid), mergesort(q, mid + 1, r);    // 递归左边、递归右边 
    int i = l, j = mid + 1, k = 0; // 递归完（就是个数从2开始，因为个数是1的话，就会在上面的l==r出直接return掉了，无返回值），用两个指针分别指向左右两边的最小位置然后进行比较 
    while(i <= mid && j <= r)  // 循环条件，只要有一边比完了，那么就不用再比下去了 剩下的那个较长的那一边就直接输出就好了 
    {
        if(q[i] < q[j]) temp[k++] = q[i++];  //  如果左边的比右边的小，就把小的那一个放在临时数组里面 然后指针再往后移 
        else temp[k++] = q[j++];    //temp[]为临时数组   同上 
    }
    while(i <= mid) temp[k++] = q[i++];   // 当右边没比完，就直接把右边存进临时数组     
    while(j <= r) temp[k++] = q[j++];  // 当左边没比完，就直接把左边存进临时数组 
    for(int i = l, k = 0; i <= r; i++, k++) q[i] = temp[k];  // 在进行完所以的操作之后，我们需要将临时数组里的数 全部返还给q数组，这样q数组就排好序了~ 
}