# C++ 64ms mergeSort

• ``````class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector<int> res; res.reserve(n);
if (n == 0) return res;
if (n == 1) {
res.push_back(0);
return res;
}
// build the mapper
vector<pair<int, int>> mapper; mapper.reserve(n);
for (int i = 0; i < n; ++i){
mapper.push_back(pair<int, int>(nums[i], i));
}
vector<int> ind(n, 0);
mapper = mergeSortCount(mapper, 0, n-1, ind);
return ind;
}
vector<pair<int, int>> mergeSortCount(vector<pair<int, int>>& nums, int left, int right, vector<int> & ind) {
if (left == right) {
vector<pair<int, int>> newVec(nums.begin() + left, nums.begin() + right + 1);
return newVec;
}
int mid = left + (right - left) / 2;
vector<pair<int, int>> small = mergeSortCount(nums, left, mid, ind);
vector<pair<int, int>> big = mergeSortCount(nums, mid+1, right, ind);
vector<pair<int, int>> res(right - left + 1, pair<int, int>(0, 0));
// cout << small[0].first << big[0].first;
int i, j;
i = j = 0;
int inv = 0;
while (i < mid - left + 1 || j < right - mid){
if (i == mid - left + 1) {
res[i + j] = big[j];
++j;
}
else if (j == right - mid) {
ind[small[i].second] += inv;
res[i + j] = small[i];
++i;
}
else if (small[i].first <= big[j].first){
ind[small[i].second] += inv;
res[i + j] = small[i];
++i;
}
else if (small[i].first > big[j].first){
++inv;
res[i + j] = big[j];
++j;
}
}
return res;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.