Unboundlocal error in mergeSort recursion

Question

I wrote the code for mergeSort from here from memory after reading it. I made the mistake of not indenting after the if statement and not including the recursive calls of mergeSort. I got the same unsorted array [54, 26, 77, 31, 44, 55, 20, 93, 17] with no errors from the interpreter.

I looked back at the reference and then realized I didn't make the recursive calls (commented out in the code below). I included them and got this error:

UnboundLocalError: local variable 'leftHalf' referenced before assignment

I don't get why this wasn't an issue before calling mergeSort recursively. I also thought that Python wasn't like C++ where variables in if statements could be referenced outside.

I know that everything after the if statement should be indented for this to be correct but would like to understand Python after bumping into this.

def mergeSort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2  # pick shorter end as left
        leftHalf = alist[:mid]
        rightHalf = alist[mid:]

    # mergeSort(leftHalf)
    # mergeSort(rightHalf)

    i = 0
    j = 0
    k = 0

    while i < len(leftHalf) and j < len(rightHalf):
        if leftHalf[i] < rightHalf[j]:
            alist[k] = leftHalf[i]
            i += 1
        else:
            alist[k] = rightHalf[j]
            j += 1
        k += 1

    # right side was all smaller and is done. Fill all left 
    while i < len(leftHalf):
        alist[k] = leftHalf[i]
        i += 1
        k += 1

    # left side was all smaller and is done. Fill all right
    while j < len(rightHalf):
        alist[k] = rightHalf[j] 
        i += 1
        k += 1

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

I looked at question 1 and question 2 and couldn't figure out how similar my case is to those in the question because I didn't define a new function.

Please read about [How to debug small programs](http://ericlippert.com/2014/03/05/how-to-debug-small-programs/). You can also use [Python-Tutor](http://www.pythontutor.com/visualize.html#mode=edit) which helps to visualize the execution of the code step-by-step. Think what happens when the function gets called with `alist` with only one item... — Tomerikoo, Dec 28 '20 at 16:22
this is a poor way to teach recursion. in [a related Q&A](https://stackoverflow.com/a/65458494/633183) from last week, i demonstrate how to write `mergesort` using recursion with a functional style. please let me know if you have follow-up questions ^^ — Mulan, Dec 28 '20 at 17:41
Thank you - I asked a follow up question your linked question. Mostly asking about what is meant by functional heritage and the issues with what you would like people to avoid. — heretoinfinity, Dec 28 '20 at 20:35

score 1 · Answer 1 · edited Dec 29 '20 at 00:51

The issue in your code is when len(alist) is not greater than one. In this case, none of the variables mid, leftHalf, or rightHalf are defined. Variables in if statements can be referenced outside the statements in Python, but the problem here is that the three variables won’t be defined if the conditional evaluates to False.

Adding an else statement AND giving values to the variables (mid, leftHalf, rightHalf) following the if statement would solve this (only adding an else without the variables doesn't solve the issue). Otherwise you could define the three variables before the if statement with some default values.

score 0 · Answer 2 · answered Feb 22 '21 at 11:33

The issue is you copied the function wrongly. From i=j=k=0 and onwards, they all should be included into the if function. The indentation is wrong.

def mergeSort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2  # pick shorter end as left
        leftHalf = alist[:mid]
        rightHalf = alist[mid:]

        # mergeSort(leftHalf)
        # mergeSort(rightHalf)

        i = 0
        j = 0
        k = 0

        while i < len(leftHalf) and j < len(rightHalf):
        if leftHalf[i] < rightHalf[j]:
            alist[k] = leftHalf[i]
            i += 1
        else:
            alist[k] = rightHalf[j]
            j += 1
        k += 1

        # right side was all smaller and is done. Fill all left 
        while i < len(leftHalf):
            alist[k] = leftHalf[i]
            i += 1
            k += 1

        # left side was all smaller and is done. Fill all right
        while j < len(rightHalf):
            alist[k] = rightHalf[j] 
            i += 1
            k += 1

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

Unboundlocal error in mergeSort recursion

2 Answers2