# My C++ merge sort solution as well

• ``````class Solution {
public:

// nums[left[i]] is the real value ,left array stores only index
vector<int> mergerArray(vector<int> left,vector<int> right,vector<int>& nums,vector<int> &res){

int lsz = left.size();
int rsz = right.size();

vector<int> re;

int i =0 , j = 0;
int cnt = 0;

while(i<lsz && j < rsz){
if(nums[left[i]] <= nums[right[j]]){
re.push_back(left[i]);
res[left[i++]] += cnt;
}else{
re.push_back(right[j++]);
cnt++;
}
}
while(i<lsz){
re.push_back(left[i]);
res[left[i++]] += cnt;
}
while(j < rsz){
re.push_back(right[j++]);
}
return re;
}

void sortArray(vector<int>& re,vector<int>& nums,vector<int>& res){
int sz = re.size();
if(sz < 2) return;
vector<int> left,right;
left.assign(re.begin(),re.begin()+sz/2);
right.assign(re.begin()+sz/2,re.end());
sortArray(left,nums,res);
sortArray(right,nums,res);
re = mergerArray(left,right,nums,res);
return;
}

vector<int> countSmaller(vector<int>& nums) {
int sz = nums.size();
vector<int> res(sz,0);
vector<int> re;
for(int i=0;i<sz;i++){
re.push_back(i);
}

sortArray(re,nums,res);
return res;
}
``````

};

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