Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement