pythonrecursionmergesort

Python exceeds recursion limit


I'm trying to develop a merge sort algorithm using divide and conqueror strategy. However during the divide portion I am getting a recursive error that I have exceeded the recursion.

Here is what I've got:

c = [3,5,4,2,1,6,7]
def mergesort(nums):
    if len(nums) == 1:
        return
    n = len(nums)//2
    a = c[:n]
    b = c [n:]
    mergesort(a)
    mergesort(b)
    i = 0
    j = 0
    k = 0

mergesort(c) 

Solution

  • It's because you're modifying the global c list rather than the argument nums list (which is your exit condition).

    c = [3,5,4,2,1,6,7]
    def mergesort(nums):
        if len(nums) == 1:
            return
        n = len(nums)//2
        a = nums[:n] # Don't use c[:n] here
        b = nums[n:] # Don't use c[n:] here
        
        print ('nums: {}\n{}\n{}\n\n'.format(nums, a, b))
        
        mergesort(a)
        mergesort(b)
    
    mergesort(c)