merge_sort_recursion.py

class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        idx = [0 for x in range(len(nums))]
        for i in range(len(nums)):
            idx[i] = (nums[i], i)
        
        # print(idx)
        result = [0 for x in range(len(nums))]
        p = self.mergeSort(idx, result)
        print(p)
        #print(result)
        return result
            
    
    def mergeSort(self, nums, result):
        if len(nums) <= 1:
            return nums
        
        mid = (int)(len(nums)/2)
        
        left = nums[0:mid]
        right = nums[mid:]
        left = self.mergeSort(left, result)
        right = self.mergeSort(right, result)
        return self.merge(left, right, result, 0)
    
    def merge(self, left, right, result, count):
        if len(left) == 0:
            return list(right) # return right (cloned)
        
        if len(right) == 0:
            for x in left:
                result[x[1]] += count
                
            return list(left) # return left (cloned)
        
        if left[0][0] > right[0][0]:
            return [right[0]] + self.merge(left,right[1:],result, count + 1)
            
        else:
            result[left[0][1]] += count
            return [left[0]] + self.merge(left[1:],right,result, count)
        
    
    def merge1(self, left, right, result):
        merged = []
        i = 0
        j = 0
        count = 0
        while i<len(left) and j<len(right):
            if left[i][0] > right[j][0]:
                count += 1 # items from right moves over
                merged.append(right[j])
                j += 1
            else:
                result[left[i][1]] += count # no more items smaller / moves over for i
                merged.append(left[i])
                i += 1
                
        # if any left is reamaining
        while i<len(left):
            result[left[i][1]] += count
            merged.append(left[i])
            i += 1 
            
        while j<len(right):
            merged.append(right[j])
            j += 1
                
        return merged
            
        
        

merge_sort_version.py

class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        idx = [0 for x in range(len(nums))]
        for i in range(len(nums)):
            idx[i] = (nums[i], i)
        
        # print(idx)
        result = [0 for x in range(len(nums))]
        p = self.mergeSort(idx, result)
        print(p)
        #print(result)
        return result
            
    
    def mergeSort(self, nums, result):
        if len(nums) <= 1:
            return nums
        
        mid = (int)(len(nums)/2)
        
        left = nums[0:mid]
        right = nums[mid:]
        left = self.mergeSort(left, result)
        right = self.mergeSort(right, result)
        return self.merge(left, right, result)
    
    def merge(self, left, right, result):
        merged = []
        i = 0
        j = 0
        count = 0
        while i<len(left) and j<len(right):
            if left[i][0] > right[j][0]:
                count += 1 # items from right moves over
                merged.append(right[j])
                j += 1
            else:
                result[left[i][1]] += count # no more items smaller / moves over for i
                merged.append(left[i])
                i += 1
                
        # if any left is reamaining
        while i<len(left):
            result[left[i][1]] += count
            merged.append(left[i])
            i += 1 
            
        while j<len(right):
            merged.append(right[j])
            j += 1
                
        return merged