1

I've been implementing a mergesort (from interactivepython) in Python/C++. The code fully works, but my issue is that I can't seem to figure out why a particular portion of the code actually does work.

Code is:

def mergeSort(alist):
    if len(alist)>1:
        mid = len(alist)//2
        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=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i<len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j<len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1

plist = [54,26,93,17]
mergeSort(plist)
print(plist)

After lefthalf = [54 26], the further subroutine split to lefthalf = [54] and righthalf = [26], the merge code works to provide alist = [26, 54] (which is the sorted left half).

Now the next step that I do in the debug window, I get a lefthalf = [26, 54]. How is this possible, as the first debug shows it defined as [54, 26] before. Where does the update to [26, 54] happen?

Any help would be super appreciated!

Improve this question
2
  • There is nothing wrong with your code. I suspect what's going on here is that your debug console is pausing after the recursive calls so that the contents of lefthalf and righthalf are sorted already. Commented Jul 22, 2015 at 23:17
  • Using the Shell Debug before running and Stepping there Commented Jul 23, 2015 at 4:10

2 Answers 2

Reset to default
1

Your mergesort function modifies the list you pass to it in place. That is, it changes the contents so that the items are in order, rather than returning a new list.

This is what you're seeing in your debugger, during the recursive calls. In the first level of the recursion, lefthalf is created by copying some values from the original list (with slice syntax). It starts out containing [54, 26]. This list is then passed to another call of mergesort. Note that the naming can get confusing, as in the inner call it refers to the list as alist (and it has its own separate lefthalf list). When the inner call returns, the contents of the outer call's lefthalf turn out to have been modified to [26, 54] (they're in order, which is what we want!).

It may be that your debugger isn't making it clear when the return is happening. Since it's all the same function (due to the recursion), it may not be obvious when the inner call ends and the control flow of the outer call resumes.

Here's a walkthrough of your code in which I show the the values of the the different variables in the various levels of the recursion as you sort your example list. Note that this isn't runnable Python code, I'm indenting to indicate the level of recursion, not for control flow. To keep the example relatively short, I'm also leaving out some steps such as as comparing the values from the two sublists and updating the i j and k indexes during the merge process:

plist = [54,26,93,17]
mergesort(plist)
    # alist is a referece to plist which contains [54,26,93,17]
    lefthalf = alist[:mid]  # new list which initially contains [54,26]
    righthalf = alist[mid:] # new list which initially contains [93,17]
    mergesort(lefthalf)
        # alist is a reference to the outer lefthalf list, which contains [54,26]
        lefthalf = alist[:mid]  # new list, initially contains [54]
        righthalf = alist[mid:] # new list, initially contains [26]
        mergesort(lefthalf)
            # alist is a reference to the previous level's lefthalf, [54]
            # the if statement doesn't pass its test, so we do nothing here (base case)
        # lefthalf was not changed by the recursive call
        mergesort(righthalf)
            # alist is a reference to the previous level's righthalf, [26]
            # base case again
        # righthalf was not changed
        alist[k]=righthalf[j] # now we merge lefthalf and righthalf back into alist
        alist[k]=lefthalf[i] # these statements change the contents of alist
    # lefthalf's contents changed, it is now sorted, [26,54]
    mergesort(righthalf)
        # alist is a reference to the outer righthalf list, which contains [93,17]
        lefthalf = alist[:mid]  # new list, initially contains [93]
        righthalf = alist[mid:] # new list, initially contains [17]
        mergesort(lefthalf) # base case, nothing happens (I'll skip the details)
        mergesort(righthalf) # base case, nothing happens
        alist[k]=righthalf[j] # merge lefthalf and righthalf back into alist
        alist[k]=lefthalf[i]  # we change the contents of alist to [17,93]
    # righthalf's contents changed, it is now sorted, [17,93]
    alist[k]=righthalf[j] # merge lefthalf and righthalf back into alist (more steps)
    alist[k]=lefthalf[i]
    alist[k]=lefthalf[i]
    alist[k]=righthalf[j] # after these statements, alist is [17,26,54,93]
# plists's contents are changed so it contains [17,26,54,93]

It might help you to step back a bit from this complex recursive situation and look at a simpler example to make sure you understand how lists can be mutated:

a = [1, 2] # create a list object with some initial contents

b = a      # b refers to the same list object as a, nothing is copied
b[1] = 3   # this modifies the list object itself, replacing the 2 with a 3

print(a)   # prints [1, 3] even through we're looking at a rather than b

def func(lst): # lst will be a new name bound to whatever is passed to the function
    lst[1] = 4 # we can modify that passed-in object (assuming it's the right type)

func(a)    # lst in the function will become another name for the list object
print(a)   # prints [1, 4]
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I've added an extra bit to the answer explaining a bit more about how mutable objects can be modified while they are bound to some other name (whether that new name comes up via a function call or just a simple assignment). I hope the whole thing helps!
0

Lists in python are mutable (ie, their contents can change) inside functions. When the list is changed inside the function, the change happens to the list that you called the function with, because it is the same list.

Therefore, the update to your list, happens every time something manipulates alist or a slice of alist, either in the first call or in any of the recursive calls.

Edit: removed misleading bit

Improve this answer

2 Comments

Your comment that slices are not new lists is misleading. When dealing with regular Python lists (rather than numpy arrays or similar), you do get a new list when you slice an existing one.
If the list is updated (i.e. alist = [26, 54, 93, 17] after the iteration we discussed above), then why does my debug window after the next step show a local alist = [54, 26, 93, 17] and lefthalf = [26, 54]? Apologies for requiring more information guys!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.