CODEWITHSUNDEEP
pythonlistpython-3.xrecursionmergesort
user2988464
user2988464

Reputation: 3461

Simple Merge Sort bug in Python

I'm doing a Merge Sort assignment in Python, but I keep have the error of RuntimeError: maximum recursion depth exceeded Here's my code:

def merge_sort(list):
    left_num = len(list) // 2
    left_sorted = merge_sort(list[:left_num])
    right_sorted = merge_sort(list[left_num:])
    final_sort = merge(left_sorted, right_sorted)
    return final_sort

def merge(left_sorted, right_sorted):
    final_sort = []
    while left_sorted and right_sorted:
        if left_sorted[0] <= right_sorted[0]:
            final_sort.append(left_sorted[0])
            left_sorted.pop(0)
        else:
            final_sort.append(right_sorted[0])
            right_sorted.pop(0)
    final_sort = final_sort + left_sorted + right_sorted
    return final_sort

if __name__ == "__main__":
    list = [4, 2]
    print(merge_sort(list))

Can someone tell me why? To make the problem more usable to others, feel free to edit the question to make it make more sense. ^_^

Upvotes: 1

Views: 114

Answers (2)

Pavel Reznikov
Pavel Reznikov

Reputation: 3208

You don't have an exit point in merge_sort. You need to do something like:

left_num = len(list) // 2
if left_num <= 1:
    return list

You always need to have a conditional exit in recursion function: if COND then EXIT else RECURSION_CALL.

Upvotes: 1

thefourtheye
thefourtheye

Reputation: 239483

When you write a recursive function, you should be careful about the base case, which decides when the recursion should come to an end.

In your case, the base case is missing. For example, if the list has only one element, then you don't have recursively sort it again. So, that is your base condition.

def merge_sort(list):
    if len(list) == 1:
        return list
    ...
    ...

Note: The variable name list shadows the builtin function list. So better avoid using builtin names.

Since you are doing lot of pop(0)s, its worth noting that it is not efficient on lists. Quoting Python's official documentation,

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

So, the better alternative would be to use collections.deque, instead of list, if you are popping a lot. The actual popping from a deque is done with popleft method.

>>> from collections import deque
>>> d = deque([4, 2])
>>> d.popleft()
4
>>> d
deque([2])

Upvotes: 4

Related Questions