Recursively calling a Merge Sort algorithm

Question

I'm new to recursion, and currently writing a Merge Sort algorithm that compares the first elements of two lists and determines which one is smaller, then adds the smaller one to a new list.

I'm trying to update the three lists after each comparison and have the function call itself again with the updated lists, but I'm getting unresolved reference issues in Pycharm and not sure what I'm doing wrong. Here is my code so far, my desired output is:

new_list = [4, 8, 15, 16, 23, 42, 50, 75, 108]

def merge_Sort(list1, list2, new_list):
    list1 = [8, 15, 16, 50, 75]
    list2 = [4, 23, 42, 108]
    new_list = []
    for i in range(len(list1)):
            if list1[0] < list2[0]:
                new_list = new_list.append(list1[0])
                list1 = list1.remove(list1[0])
                break


            elif list1[0] > list2[0]:
                new_list = new_list.append(list2[0])
                list2 = list2.remove(list2[0])
                break

    merge_Sort(list1, list2, new_list)

merge_Sort(list1, list2, new_list)

Answer 1

Your code lead to infinite recursion. You should move list1,list2 and new_list initialization outside of merge_Sort function.

def merge_Sort(list1, list2, new_list):
    for i in range(len(list1)):
        if list1[0] < list2[0]:
            new_list.append(list1[0])
            list1.remove(list1[0])
            break
        elif list1[0] > list2[0]:
            new_list.append(list2[0])
            list2.remove(list2[0])
            break

    merge_Sort(list1, list2, new_list)

list1 = [8, 15, 16, 50, 75]
list2 = [4, 23, 42, 108]
new_list = []
merge_Sort(list1, list2, new_list)