# C++ solution with Divide and Conquer

• ``````class Solution {
public:
void mergesort(vector<int>& nums,vector<int> &tag,int start,int mid,int end){
if(start==end)  return;
int k=0,st=start;
vector<int> tg(end-start+1);
for(int i=0;i<end-start+1;i++) tg[i]=tag[st++];
vector<int> tp(end-start+1);
int s1=start,e1=mid-1,s2=mid,e2=end;
while(s1<=e1&&s2<=e2){
if(nums[s1]<nums[s2]){
tp[k++]=nums[s1++];
tag[start+k-1]=tg[s1-start-1];
}
else{
tp[k++]=nums[s2++];
tag[start+k-1]=tg[s2-start-1];
}
}
while(s1<=e1){
tp[k++]=nums[s1++];
tag[start+k-1]=tg[s1-start-1];
}
while(s2<=e2){
tp[k++]=nums[s2++];
tag[start+k-1]=tg[s2-start-1];
}
for(int i=0;i<k;i++)   nums[start+i]=tp[i];
}
void countnumber(vector<int>& nums,vector<int>& result,vector<int>& tag,int start,int end){
if(start+1==end){ result[tag[start]]=0;return;}
int mid=(start+end)>>1;
countnumber(nums,result,tag,start,mid);
countnumber(nums,result,tag,mid,end);
int c=0,r=mid;
for(int i=start;i<mid;i++){
while(r<end&&nums[r]<nums[i]){
c++;r++;
}
result[tag[i]]+=c;
}
mergesort(nums,tag,start,mid,end-1);
}

vector<int> countSmaller(vector<int>& nums) {
int len=(int)nums.size();
vector<int> result(len),tag(len);
if(len==0)  return result;
for(int i=0;i<len;i++) tag[i]=i;
countnumber(nums,result,tag,0,len);
return result;
}
};``````

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