归并排序

//将arr[l,mid]和arr[mid+1,r]两部分进行归并
template<typename T>
void __merge(T arr[], int l, int mid, int r) {//确定元素放置在原数组中的位置
    T aux[r - l + 1];
    for(int i=l;i<=r;i++){
        aux[i-l] == arr[i];
    }
    int i = l, j = mid + 1;
    for (int k = l; k <= r; k++) {
        if(i>mid){//判断是否越界
            arr[k] = aux[j-l];
            j++;
        }
        else if (j > r) {//判断是否越界
            arr[k] = aux[i - l];
            i++;
        }
        else if (aux[i - l] < aux[j - l]) {//如果i-1小，i-1就放入k中
            arr[k] = aux[i - l];
            i++;
        }
        else {//如果j-1小，j-1就放入k中
            arr[k] = aux[j - l];
            j++;
        }
    }
}

//递归使用归并排序，对arr[l,r]范围进行排序
template <typename T>
void __mergeSort(T arr[], int l, int r) {
    if (l >= r) {//一个元素都没有，数据集为空
        return;
    }
    int mid = (l + r) / 2;
    __mergeSort(arr, l, mid);//左半部分归并排序
    __mergeSort(arr, mid + 1, r);//右半部分归并排序
    __merge(arr, l, mid, r);//归并
}

template<typename T>
void mergeSort(T arr[], int n) {
    __mergeSort(arr, 0, n - 1);//第n个是空的，n-1有值
}