# Mergesort solution in C++

• ``````class Solution
{
public:
struct IndexNumber
{
int Number;
int Index;
IndexNumber(int n, int i)
{
Number = n;
Index = i;
}

IndexNumber()
{
Number = Index = 0;
}
};

vector<int> countSmaller(vector<int>& nums)
{
if (nums.size() == 0) return vector<int>();

vector<int> state(nums.size(), 0);
vector<IndexNumber> numbers;
for (int i = 0; i < nums.size(); i++)
{
IndexNumber in(nums[i], i);
numbers.push_back(in);
}

merge(numbers, 0, nums.size() - 1, state);

return state;
}

void merge(vector<IndexNumber>& nums, int start, int end, vector<int>& state)
{
if (start == end)
{
return;
}

int mid = (start + end) / 2;
merge(nums, start, mid, state);
merge(nums, mid + 1, end, state);

vector<IndexNumber> ret(end - start + 1, IndexNumber());
int p0 = 0;
int p1 = start;
int p2 = mid+1;

while (p0 < ret.size())
{
while (p1 <=mid && p2<=end && nums[p1].Number <= nums[p2].Number)
{
ret[p0++] = nums[p1++];
}

int count = 0;
while (p1 <=mid && p2<=end && nums[p1].Number>nums[p2].Number)
{
count++;
ret[p0++] = nums[p2++];
}

for (int t = p1; t <=mid; t++)
{
state[nums[t].Index] += count;
}

if (p1 == mid+1)
{
for (int t = p2; t <=end; t++)
{
ret[p0++] = nums[t];
}
}

if (p2 == end+1)
{
for (int t = p1; t <=mid; t++)
{
ret[p0++] = nums[t];
}
}
}

for (int i = 0; i < ret.size(); i++)
{
nums[start + i] = ret[i];
}
}
};``````

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