合并排序

std::vector<int> temp;
void merge(std::vector<int>& arr, int l, int mid, int r) {
    std::copy(arr.begin() + l, arr.begin() + r, temp.begin() + l);
    int p = l, q = mid;
    for (int i = l; i < r; i++) {
        if (q >= r || (p < mid && arr[p] < arr[q])) {
            temp[i] = arr[p++];
        } else {
            temp[i] = arr[q++];
        }
    }
    std::copy(temp.begin() + l, temp.begin() + r, arr.begin() + l);
}

void mergeSort(std::vector<int>& arr, int l, int r) {
    if (r - l == 1) {
        return ;
    }
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid, r);
    merge(arr, l, mid, r);
}

void mergeSort(std::vector<int>& arr) {
    temp.resize(arr.size());
    mergeSort(arr, 0, (int) arr.size());
}