Count of Smaller Numbers After Self in an Array

Problem: 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:

Input: nums = [5,3,1,2]
Output: [3,2,0,0]
Explanation:
To the right of 5 there are 3 smaller elements (3, 1 and 2).
To the right of 3 there are 2 smaller element (1 and 2).
To the right of 1 there are no smaller element.
To the right of 1 there is 0 smaller element.

Approach: This is a clearly a problem of finding the number of inversions. Now here instead of finding total number of inversions, we need to find inversions per element/index in the array. We will use the same merge sort approach here but here for simplicity I am sorting indices instead of actual array as we need to fill result array according to how many numbers are less than on the right of the index. 

You can use original merge sort too. You can also use any balanced binary tree to solve this problem.  

Implementation in C#:

        public static IList<int> CountSmaller(int[] nums) 

        {

            int[] result = new int[nums.Length];

            int[] indexes = Enumerable.Range(0, nums.Length).ToArray();

            CountSmallerNumberUsingMergeSort(ref indexes, nums, result);

            return result.ToList();

        }

        private static void CountSmallerNumberUsingMergeSort(ref int[] indexes, int[] nums, int[] result)

        {

            if (indexes.Length <= 1)

            {

                return;

            }

            int[] leftArray = indexes.SubArray(0, indexes.Length / 2);

            int[] rightArray = indexes.SubArray(indexes.Length / 2, indexes.Length - indexes.Length / 2);

            CountSmallerNumberUsingMergeSort(ref leftArray, nums, result);

            CountSmallerNumberUsingMergeSort(ref rightArray, nums, result);

            indexes = CountSmallerWhileMerge(leftArray, rightArray, nums, result);

        }

        private static int[] CountSmallerWhileMerge(int[] leftArray, int[] rightArray, int[] nums, int[] result)

        {

            int lIndex = 0, rIndex = 0;

            int countOfSmallerNumber = 0;

            List<int> newIndexes = new List<int>();

            while (lIndex < leftArray.Length && rIndex < rightArray.Length)

            {

                if (nums[leftArray[lIndex]] > nums[rightArray[rIndex]])

                {

                    ++countOfSmallerNumber;

                    newIndexes.Add(rightArray[rIndex++]);

                }

                else

                {

                    result[leftArray[lIndex]] += countOfSmallerNumber;

                    newIndexes.Add(leftArray[lIndex++]);

                }

            }

            while(lIndex < leftArray.Length)

            {

                result[leftArray[lIndex]] += countOfSmallerNumber;

                newIndexes.Add(leftArray[lIndex++]);

            }

            while(rIndex < rightArray.Length)

            {

                newIndexes.Add(rightArray[rIndex++]);

            }

            return newIndexes.ToArray();

        }

        

        // Put this extension method in a static class if you want to use it as is

        public static T[] SubArray<T>(this T[] array, int startIndex, int length)

        {

            T[] subArray = new T[length];

            Array.Copy(array, startIndex, subArray, 0, length);

            return subArray;

        }

Complexity: O(nlogn)