having trouble with merge sort

Question

I felt like I have the algorithm down pretty well but don't know why I cant get a correct output. I think its something with the recursion but I'm having trouble debugging.

def merge(front, back):
    i = 0 
    j = 0 
    k = 0
    while i < len(front) and j < len(back):
        if front[i] < back[j]:
            x[k] = front[i]
            i = i+1
        else:
            x[k] = back[j]
            j = j+1
        k = k+1
            
        while(i < len(front)):
            x[k] = front[i]
            i = i +1
            k = k+1
                
        while(j < len(back)):
            x[k] = back[j]
            j = j +1
            k = k+1
        return x
    
def mergeSort(x):
    if len(x) > 1:
        front = x[:len(x)//2]
        back = x[len(x)//2:]
        mergeSort(front)
        mergeSort(back)
        merge(front,back)
       
       

x = [12,11,13,5,6,7] 
mergeSort(x)       
print(x)

output: [5, 12, 11, 13, 6, 7]

Answer 1

The main issue that's causing you grief is the variable x in the merge function.

Note that when you call merge you're making changes to x. x is not defined in the local namespace, nor in the enclosing namespace. So it keeps looking until it reaches the global namespace. The x defined in the global namespace is [12,11,13,5,6,7] so it is making changes on this x.

In order to address this, simply feed the x from mergeSort into the merge. This behavior is likely occurring due to the recursive nature of the mergeSort function.

You can learn more about namespaces and variable scopes here.

There is also the issue with your nested while loops. You don't want to execute the second and the third while loops until the first while loop has completed. The stopping condition of the first while loop is that either front or back has been completely sorted.

def merge(front, back, x):
    i = 0 
    j = 0 
    k = 0
    while i < len(front) and j < len(back):
        if front[i] < back[j]:
            x[k] = front[i]
            i = i+1
        else:
            x[k] = back[j]
            j = j+1
        k = k+1
    
    #These two while loops have been moved back one indentation
    #to run after the first while loop stops
    while(i < len(front)):
        x[k] = front[i]
        i = i +1
        k = k+1
            
    while(j < len(back)):
        x[k] = back[j]
        j = j +1
        k = k+1
    return x
    
def mergeSort(x):
    if len(x) > 1:
        front = x[:len(x)//2]
        back = x[len(x)//2:]
        mergeSort(front)
        mergeSort(back)
        merge(front,back, x)       

x = [12,11,13,5,6,7] 
mergeSort(x)       
print(x) #output is [5,6,7,11,12,13] as desired