MergeSort.cpp

MergeSort.cpp

void merge(vector<int> &a, vector<int> &temp, int mid, int leftStart, int rightEnd) {
    int leftEnd = mid;
    int rightStart = leftEnd + 1;
    int curIndex = leftStart, left = leftStart;
    for (;leftStart <= leftEnd && rightStart <= rightEnd;) {
        if (a[leftStart] <= a[rightStart])
            temp[curIndex++] = a[leftStart++];
        else
            temp[curIndex++] = a[rightStart++], res += leftEnd - leftStart + 1;
    }
    for (;leftStart <= leftEnd;) temp[curIndex++] = a[leftStart++];
    for (;rightStart <= rightEnd;) temp[curIndex++] = a[rightStart++];
    for (int i = left; i <= rightEnd; i++) a[i] = temp[i];
}


void mergesort(vector<int> &a, vector<int> &temp, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergesort(a, temp, left, mid);
    mergesort(a, temp, mid + 1, right);
    merge(a, temp, mid, left, right);
}