Recursion depth exceeding in a python function for counting reverse pairs

Question

I am trying to find reverse pairs using this code, but recursion depth is exceeding. This code is just a variation of MergeSort algorithm

class Solution(object):
        
    def reversePairs(self, nums):
        def merge(nums, temp, left, mid, right):
            revcount = 0
            j = mid
            
            for i in range(mid):
                while j < right and nums[i] > 2*(nums[j]):
                    j += 1
                revcount += j-mid
                
            j = mid
            i = left
            k = left
            
            while i < mid and j < right:
                if nums[i] < nums[j]:
                    temp[k] = nums[i]
                    i += 1
                    k += 1
                else:
                    temp[k] = nums[j]
                    j += 1
                    k += 1
                
            while i < mid:
                temp[k] = nums[i]
                i += 1
                k += 1
            while j < right:
                temp[k] = nums[j]
                j += 1
                k += 1
                
            for i in range(left, right):
                nums[i] = temp[i]
            return revcount

        def mergeSort(nums, temp, left, right):
            revcount = 0
            if left < right:
                mid = (left + right) // 2
                revcount += mergeSort(nums, temp, left, mid)
                revcount += mergeSort(nums, temp, mid, right)
                revcount += merge(nums, temp, left, mid, right)
            return revcount
        
        n = len(nums)
        temp = [0] * n
        return mergeSort(nums, temp, 0, n)

Maximum recursion depth exceeding in line revcount += mergeSort(nums, temp, left, mid)

Can someone tell me what is wrong with above code.

Answer 1

To solve the recursion depth issue, you must stop recursing when the slice has fewer than 2 elements, ie: replace the test if left < right: with

    if right - left > 1:

Note that the inversion count calculation seems broken:

        j = mid
        for i in range(mid):
            while j < right and nums[i] > 2*(nums[j]):
                j += 1
            revcount += j-mid
            

for i in range(mid) iterates over a much wider range than needed. You should iterate from left to mid (excluded), hence for i in range(left, mid)

Futhermore testing nums[i] > 2*(nums[j]) seems inconsistent.

To count the number of inversions, you can just update revcount in the merge loops whenever you take an element from the right slice:

        while i < mid and j < right:
            if nums[i] < nums[j]:
                temp[k] = nums[i]
                i += 1
                k += 1
            else:
                temp[k] = nums[j]
                j += 1
                k += 1
                revcount += j-k

Answer 2

Isolating your merge sort splitting logic and testing on a small size yields the following:

def split(left, right):
    print(left, right)
    if left < right:
        mid = (left + right) // 2
        split(left, mid)
        split(mid, right)
split(0, 1024)

this will continously print 0 0 and 0 1. The reason for this is that if left = 0 and right = 1, you get mid = 0. The second recursive call then becomes mergeSort(0, 1) - that is, it continues with left = 0 and right = 1. Rinse and repeat - this recurses infinitely. The fix for this is to simply tighten the exit condition, slightly improving performance by ensuring that the array contains more than one element:

def mergeSort(nums,temp,left,right):
    revcount = 0
    mid=(left+right)//2
    if mid == left: return revcount # empty (left == right) or only one element (left + 1 == right)
    revcount+=mergeSort(nums,temp,left,mid)
    revcount+=mergeSort(nums,temp,mid,right)
    revcount+=merge(nums,temp,left,mid,right)
    return revcount