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


Answer: 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.

