归并排序

 1class Solution {
 2public:
 3    int merge(vector<int> &a, vector<int> &t, int l, int m, int r)
 4    {
 5        for (int i = l; i <= r; ++i)
 6            t[i] = a[i];
 7
 8        int inv = 0, i = l, j = m + 1;
 9        for (int k = l; k <= r; ++k) {
10            if (i > m)
11                a[k] = t[j++];
12            else if (j > r)
13                a[k] = t[i++];
14            else if (t[i] <= t[j])
15                a[k] = t[i++];
16            else {
17                a[k] = t[j++];
18                inv += m - i + 1;  // 左边有序，i~m 都大于 j
19            }
20        }
21        return inv;
22    }
23
24    int msort(vector<int> &a, vector<int> &t, int l, int r)
25    {
26        if (l >= r) return 0;
27        int inv = 0, m = l + (r - l) / 2;
28        inv += msort(a, t, l, m);
29        inv += msort(a, t, m + 1, r);
30        inv += merge(a, t, l, m, r);
31        return inv;
32    }
33
34    int reversePairs(vector<int> &record)
35    {
36        vector<int> tmp(record.size());
37        return msort(record, tmp, 0, record.size() - 1);
38    }
39};