Why my merge sort in python exceeded maximum recursion depth?

Question

I am learning MIT's open course 6.046 "Introduction to Algorithms" in Youtube, and I was trying to implement the merge sort in python.

My code is

def merge(seq_list, start, middle, end):
    left_list = seq_list[start:middle]
    left_list.append(float("inf"))
    right_list = seq_list[middle:end]
    right_list.append(float("inf"))
    i = 0
    j = 0
    for k in range(start, end):
        if left_list[i] < right_list[j]:
            seq_list[k] = left_list[i]
            i = i + 1
        else:
            seq_list[k] = right_list[j]
            j = j + 1


def merge_sort(seq_list, start, end):
    if start < end:
        mid = len(seq_list)/2
        merge_sort(seq_list[0:mid], start, mid)
        merge_sort(seq_list[mid:], mid, end)
        merge(seq_list, start, mid, end)

And the unittest code is

import unittest
from sorting import *

class SortingTest(unittest.TestCase):
    def testMergeSort(self):
        test_list = [3, 4, 8, 0, 6, 7, 4, 2, 1, 9, 4, 5]
        merge_sort(test_list, 0, 9)
        self.assertEqual(test_list, [0, 1, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9])
    def testMerge(self):
        test_list = [13,17,18,9,2,4,5,7,1,2,3,6,0,38,12]
        merge(test_list, 4, 8, 12)
        self.assertEqual(test_list, [13,17,18,9,1,2,2,3,4,5,6,7,0,38,12])


if __name__ == "__main__":
    unittest.main()

The function merge() seems work perfectly, but the merge_sort() function was wrong, and I don't know what's going on. The terminal show me:

RuntimeError: maximum recursion depth exceeded

Why do you call merge_sort with end=9 when len(test_list) == 12? — Michael J. Barber

amit amit · Accepted Answer · 2012-03-28T08:41:58

You need to add a base clause when the list is empty or of size 1, other wise you keep "shrinking" an empty list, [and actually stay with the same list].

EDIT:

Also, I think it is actually deriving from a different bug: you are using len(seq) some times, and start,end sometimes - you should just stick to one of them.

    mid = len(seq_list)/2
    merge_sort(seq_list[0:mid], start, mid)
    merge_sort(seq_list[mid:], mid, end)

Have a look on the test case [0,1,2,3]

start = 0, end = 3 -> mid = 2

Now you recurse with

mergesort([2,3],2,3) #2 == mid, 3 == end

And later you will set:

mid = len([2,3])/2 == 1

and try recursing again with

mergesort([3],1,3)

You will never reach the "stop condition" of start >= end, because end never changes, and is out of the current list's bounds!

Another bug:

merge_sort(seq_list[0:mid], start, mid)

does not do anything on seq_list, it does not change it - it only changes the new list object you passd to the recursion, and thus merge() will also fail.

Why my merge sort in python exceeded maximum recursion depth?

1 Answers