Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

Python

Posted by Brian Pitts
Brian Pitts
Courses Plus Student 3,826 Points

merge sort in python

Hello. I was going through a tutorial on implementing the merge sort algorithm in python but couldn't get it to work. Worse yet, I can't seem to figure out the error. If someone has a clue or hint as to what the problem is, that would be appreciated. Thanks!

def merge_sort(A):
    sorted_list = merge_sort2(A, 0, len(A)-1)
    return sorted_list

def merge_sort2(A, first, last):
    if first < last:
        middle = (first + last) // 2
        merge_sort2(A, first, middle)
        merge_sort2(A, middle+1, last)
        merge(A, first, middle, last)


def merge(A, first, middle, last):
    L=A[first:middle]
    R=A[middle:last+1]
    L.append(99999)
    R.append(99999)
    i=j=0
    for k in range (first, last+1):
        if L[i]<=R[j]:
            A[k]=L[i]
            i +=1
        else:
            A[k] = R[j]
            j+=1


print (merge_sort([1,5,6,2,7,9]))

ref: https://www.youtube.com/watch?v=Nso25TkBsYI

2 Answers

Chris Freeman
MOD
Chris Freeman
Treehouse Moderator 68,468 Points
Chris Freeman
Chris Freeman
Treehouse Moderator 68,468 Points

I modified the merge code to add print statements to watch the progress

def merge(A, first, middle, last):
    print("merge start A:{}, f:{}/m:{}/l:{}".format(A, first, middle, last))
    L = A[first:middle]
    R = A[middle:last + 1]
    print("merge start L:{}, R:{}".format(L, R))
    L.append(99999)
    R.append(99999)
    i = j = 0
    for k in range(first, last + 1):
        if L[i] <= R[j]:
            print("A[{}] became L[{}]: {}->{}".format(k, i, A[k], L[i]))
            A[k] = L[i]
            i += 1
        else:
            print("A[{}] became R[{}]: {}->{}".format(k, j, A[k], R[j]))
            A[k] = R[j]
            j += 1
    print("merge end A:{}".format(A))

The results show the last merge failing due to the selection of middle for the call to merge:

$ python merge-sort.py 
merge start A:[1, 5, 6, 2, 7, 9], f:0/m:0/l:1
merge start L:[], R:[1, 5]
A[0] became R[0]: 1->1
A[1] became R[1]: 5->5
merge end A:[1, 5, 6, 2, 7, 9]
merge start A:[1, 5, 6, 2, 7, 9], f:0/m:1/l:2
merge start L:[1], R:[5, 6]
A[0] became L[0]: 1->1
A[1] became R[0]: 5->5
A[2] became R[1]: 6->6
merge end A:[1, 5, 6, 2, 7, 9]
merge start A:[1, 5, 6, 2, 7, 9], f:3/m:3/l:4
merge start L:[], R:[2, 7]
A[3] became R[0]: 2->2
A[4] became R[1]: 7->7
merge end A:[1, 5, 6, 2, 7, 9]
merge start A:[1, 5, 6, 2, 7, 9], f:3/m:4/l:5
merge start L:[2], R:[7, 9]
A[3] became L[0]: 2->2
A[4] became R[0]: 7->7
A[5] became R[1]: 9->9
merge end A:[1, 5, 6, 2, 7, 9]
merge start A:[1, 5, 6, 2, 7, 9], f:0/m:2/l:5
merge start L:[1, 5], R:[6, 2, 7, 9]
A[0] became L[0]: 1->1
A[1] became L[1]: 5->5
A[2] became R[0]: 6->6
A[3] became R[1]: 2->2
A[4] became R[2]: 7->7
A[5] became R[3]: 9->9
merge end A:[1, 5, 6, 2, 7, 9]
None

Changing merge_sort2 to increment middle by one in the merge call:

def merge_sort2(A, first, last):
    if first < last:
        middle = (first + last) // 2
        merge_sort2(A, first, middle)
        merge_sort2(A, middle + 1, last)
        merge(A, first, middle + 1, last)  # <-- increment middle by one

Seemed to do the trick:

$ python merge-sort.py 
merge start A:[1, 5, 6, 2, 7, 9], f:0/m:1/l:1
merge start L:[1], R:[5]
A[0] became L[0]: 1->1
A[1] became R[0]: 5->5
merge end A:[1, 5, 6, 2, 7, 9]
merge start A:[1, 5, 6, 2, 7, 9], f:0/m:2/l:2
merge start L:[1, 5], R:[6]
A[0] became L[0]: 1->1
A[1] became L[1]: 5->5
A[2] became R[0]: 6->6
merge end A:[1, 5, 6, 2, 7, 9]
merge start A:[1, 5, 6, 2, 7, 9], f:3/m:4/l:4
merge start L:[2], R:[7]
A[3] became L[0]: 2->2
A[4] became R[0]: 7->7
merge end A:[1, 5, 6, 2, 7, 9]
merge start A:[1, 5, 6, 2, 7, 9], f:3/m:5/l:5
merge start L:[2, 7], R:[9]
A[3] became L[0]: 2->2
A[4] became L[1]: 7->7
A[5] became R[0]: 9->9
merge end A:[1, 5, 6, 2, 7, 9]
merge start A:[1, 5, 6, 2, 7, 9], f:0/m:3/l:5
merge start L:[1, 5, 6], R:[2, 7, 9]
A[0] became L[0]: 1->1
A[1] became R[0]: 5->2
A[2] became L[1]: 6->5
A[3] became L[2]: 2->6
A[4] became R[1]: 7->7
A[5] became R[2]: 9->9
merge end A:[1, 2, 5, 6, 7, 9]
None

Note that None is printed because merge_sort2 doesn't return anything. Since all of the functions are operating directly on A, perhaps change the merge_sort return to return A

Brian Pitts
PLUS
Brian Pitts
Courses Plus Student 3,826 Points
Brian Pitts
Brian Pitts
Courses Plus Student 3,826 Points

Thank you, Chris. Adding print statements helped me to follow the recursive function. Nice pick up on needing to add +1 to 'middle' in the final call to merge.