<p>Given an integer array <code>nums</code>, return<em> an integer array </em><code>counts</code><em> where </em><code>counts[i]</code><em> is the number of smaller elements to the right of </em><code>nums[i]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,2,6,1]
<strong>Output:</strong> [2,1,1,0]
<strong>Explanation:</strong>
To the right of 5 there are <b>2</b> smaller elements (2 and 1).
To the right of 2 there is only <b>1</b> smaller element (1).
To the right of 6 there is <b>1</b> smaller element (1).
To the right of 1 there is <b>0</b> smaller element.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1]
<strong>Output:</strong> [0]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1,-1]
<strong>Output:</strong> [0,0]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>


import heapq
import numpy as np
from collections import deque

class Merger:
    def __init__(self, size):
        self.sorts = [0] * size

    # def merge(self, left, right):
    #     result = []
    #     l, r = 0, 0
    #     while l < len(left) or r < len(right):
    #         if r >= len(right) or (l < len(left) and left[l][1] <= right[r][1]):
    #             result.append(left[l])
    #             self.sorts[left[l][0]] += r
    #             l += 1
    #         else:
    #             result.append(right[r])
    #             r += 1
    #     return result

    def merge_sort(self, arr, key):
        start = 0
        end = len(arr)
        if len(arr) == 0:
            return []
        if len(arr) == 1:
            return [arr[start]]

        mid = (end - start) // 2


        left = self.merge_sort(arr[:mid], key) if len(arr[:mid]) > 1 else arr[:mid]
        right = self.merge_sort(arr[mid:], key) if len(arr[mid:]) > 1 else arr[mid:]
        # return self.merge(left, right)
        if left[-1][0] > right[0][0]:
            return left + right

        r = []
        lind = 0
        rind = 0

        while lind < len(left) and rind < len(right):
            
            if left[lind][1] <= right[rind][1] :
                
                r.append(right[rind])
                rind += 1
            else:
                # print(f"left={left[lind:]} right={right[rind:]} ", self.sorts[left[lind][0]])
                # print(len(right[rind:]), rind)
                self.sorts[left[lind][0]] += len(right)-rind
                
                r.append(left[lind])
                lind += 1

        if len(left[lind:]) > 0:
            return r + left[lind:]
        if len(right[rind:]) > 0:
            return r + right[rind:]
        
        return r
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        start = 0
        end = len(nums)
   
        merger = Merger(end-start)
        merger.merge_sort(list(enumerate(nums)), key=lambda a,b: a[1]-b[1])

        return merger.sorts 

                
55820