# CPP solution based on the idea of merge_sort

• ``````class Solution {
vector<pair<int, int> > x;
vector<int> ans;
public:
vector<int> countSmaller(vector<int>& nums) {
for (int i = 0; i < nums.size(); i++) x.push_back(make_pair(nums[i], i));
ans = vector<int>(x.size(), 0);
merge_sort(0, x.size() - 1);
return ans;
}

void merge_sort(int start, int end) {
if (end <= start) return;
int mid = start + (end - start) / 2;
merge_sort(start, mid);
merge_sort(mid + 1, end);
merge(start, mid, mid + 1, end);
}

void merge(int start1, int end1, int start2, int end2) {
vector<pair<int, int> > tmp;
int p = start1, q = start2;
while (p <= end1 && q <= end2) {
if (x[p].first <= x[q].first) {
ans[x[p].second] += q - start2;
tmp.push_back(x[p++]);
} else {
tmp.push_back(x[q++]);
}
}
while (p <= end1) {
ans[x[p].second] += q - start2;
tmp.push_back(x[p++]);
}
while (q <= end2) tmp.push_back(x[q++]);
for (int i = start1; i<= end2; i++) x[i] = tmp[i - start1];
}
};``````

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