Count of the smaller number after self (CSNAS)” is a Algorithms Problem in LeetCode. It is considered as a Hard issue but can be solved by Merge Sort algorithm in an efficient way. In my project, I encounter a problem which is quite similar to problem CSNAS, and I call it as Weighted Count of the Smaller Number After Self (WCSNAS) problem. Before introducing the WCSNAS problem and related efficient solution, we first describe the CSNAS in the following.

### Problem Description for CSNAS

• You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

### Problem Description for WCSNAS

• You are given two arrays, the first array is an integer array nums and the second array is a double array weight. You have to return a new _weight_counts_ array. The counts array has the property where wcounts[i] is the summation of weights of smaller elements to the right of nums[i].

Example:

### Solve WCSNAS with Merge Sort

StefanPochmann suggest a merge sort
solution for CSNAS with merge sort: “The smaller numbers on the right of a number are exactly those that jump from its right to its left during a stable sort. So I do mergesort with added tracking of those right-to-left jumps.”

My solution mimic the solution of CSNAS by adding tracking of those right-to-left jumps for weight array. The source code implemented in C++ is shown below.

Donate