315. Count of Smaller Numbers After Self

class Solution:
    def countSmaller(self, A: List[int]) -> List[int]:
        n = len(A)
        res = [0] * n 
        B = [] 
        for i, v in enumerate(A):
            B.append((v,i))
        
        def merge(l_arr, r_arr):
            """tc O(NlgN) sc O(N)
            1. when both left array and right array is not running out, compare left[l] with right[r], move it onto merged array,
            2. if right element move before left element, update state accumutate. otherwise, add offset onto final result array while append smaller to merged element 
            3. when one of the subarray run out, go through remaining array and append them onto merged array 
            4. update offset to final result array if it is left arrray that remains 
            
            """
            l, r, r2l = 0,0,0
            merged_tmp = []
            
            while l < len(l_arr) and r < len(r_arr):
                
                if l_arr[l][0] > r_arr[r][0]:
                    merged_tmp.append(r_arr[r]) # note merged temporary array can't be inserted value only, need to be same format as input array 
                    r2l += 1 
                    r += 1 
                else:
                    merged_tmp.append(l_arr[l])
                    res[l_arr[l][1]] += r2l  # right to left swap accumulative count  
                    l += 1 
                    
            while r < len(r_arr):
                merged_tmp.append(r_arr[r])
                r += 1
                
                
            while l < len(l_arr):
                merged_tmp.append(l_arr[l])
                res[l_arr[l][1]] += r2l 
                l += 1 
            
            return merged_tmp # merged sorted subarray   
        
        def sort(A):
            if len(A) == 1:
                return A
            mid = len(A)//2
            left = sort(A[:mid])
            right = sort(A[mid:])
            return merge(left, right)
        sort(B)
        return res