# Share my C++ MergeSort solution

• In this problem we only need to count the number of `nums[j]` < `nums[i]` while `j > i`; So we can doing this while doing MergeSort.

Assume after MergeSort, now we have the `left part` and the `right part` which are all in order. And we can know that all nums in `right part` is definitely on the right side of those `left part` nums, then for each num in `left part` we can count the nums smaller in the `right part`.

Because we are doing this after MergeSort `left part` and `right part`, which means for each num in `left part` we have completely get the res in the `left part` domain, so do within the `right part`. In this way, for each num in `left part`, we have count the possible ans in `left part`, then we need to count those nums in `right part`. As to num in `right part`, we need to go through and count in its `right part`.

Because the `right part` is in order, so we just need to go through one time!
Codes below using two `vector<int>` to store the copy of nums and update indices;

Final Codes

``````class Solution
{
public:
vector<int> countSmaller(vector<int> &nums)
{
int len = nums.size();
vector<int> res(len, 0);
vector<int> index;
for(int i = 0; i < len; ++i)
index.push_back(i);
vector<int> numUpdate = nums;
vector<int> indexUpdate = index;
solve(res, nums, index, 0, len, numUpdate, indexUpdate);
return res;
}
void solve(vector<int> &res, vector<int> &nums, vector<int> &index, int start, int end, vector<int> &numUpdate, vector<int> &indexUpdate)
{
if(end - start <= 1)
return;
int mid = (start + end) / 2;
solve(res, nums, index, mid, end, numUpdate, indexUpdate);
solve(res, nums, index, start, mid, numUpdate, indexUpdate);
int r = mid;
int t = mid;
int s = start;
for(int l = start; l < mid; ++l)
{
while(nums[l] > nums[r] && r < end)
r++;
while(t < end && nums[t] <= nums[l])
{
numUpdate[s] = nums[t];
indexUpdate[s++] = index[t++];
}
numUpdate[s] = nums[l];
indexUpdate[s++] = index[l];
res[index[l]] += r - mid;
}
for(int i = start; i < end; ++i)
{
nums[i] = numUpdate[i];
index[i] = indexUpdate[i];
}
}
};
``````

Older Version Codes
And the older version codes below, using a `vector<pair<int, int>>` to store the values and index, but using `sort` is not so efficient.

``````bool cmp(const pair<int, int> a, const pair<int, int> b)
{
return a.first < b.first;
}

class Solution
{
public:
vector<int> countSmaller(vector<int> &nums)
{
int len = nums.size();
vector<int> res(len, 0);
vector<pair<int, int>> temp;
for(int i = 0; i < len; ++i)
temp.push_back(make_pair(nums[i], i));
solve(res, temp, 0, len);
return res;
}
void solve(vector<int> &res, vector<pair<int, int>> &temp, int start, int end)
{
if(end - start <= 1)
return;
int mid = (start + end) / 2;
solve(res, temp, mid, end);
solve(res, temp, start, mid);
int r = mid;
for(int l = start; l < mid; ++l)
{
while(temp[l].first > temp[r].first && r < end)
r++;
res[temp[l].second] += r - mid;
}
sort(temp.begin() + start, temp.begin() + end, cmp);
}
};
``````

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