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 trialKong Tat Ong
5,145 PointsWhat am I doing wrong?
I tried to implement this without slicing and when I ran through the whole thing step by step, it should run smoothly but it says that I exceeded the recursion depth, but I do not know which part of the code is doing the recursion multiple times. May I know where did I go wrong?
def merge_sort(list, start = 0, end = None):
"""
Sorts a list in ascending order
Returns a new sorted list
Divide: Find the midpoint for the list and divide into sublists
Conquer: Recursively sort the sublists created in previous step
Combine: Merge the sorted sublists created in previous step
"""
a = []
if end is None:
end = len(list) - 1
if start > end:
return -1
if start == end:
a.append(list[start])
return a
left_start, left_end, right_start, right_end = split(list, start, end)
left = merge_sort(list, left_start, left_end)
right = merge_sort(list, right_start, right_end)
return merge(left, right)
def split(list, start, end):
if (end - start) == 1:
return start, start, end, end
left_start = start
left_end = end // 2
right_start = left_end + 1
right_end = end
#left = list[:mid]
#right = list[mid:]
return left_start, left_end, right_start, right_end
def merge(left, right):
i = []
r = 0
l = 0
while l < len(left) and r < len(right):
if left[l] < right[r]:
i.append(left[l])
l += 1
else :
i.append(right[r])
r += 1
while l < len(left) :
i.append(left[l])
l +=1
while r < len(right) :
i.append(right[r])
r +=1
return i
def verify_sorted(list):
n = len(list)
if n == 0 or n == 1:
return True
return list[0]<list[1] and verify_sorted(list[ 1:])
alist = [5, 3, 6, 9, 10, 15, 100, 50]
merge_sort(alist)
print(verify_sorted(alist))
1 Answer
Steven Parker
231,248 PointsI'd suggest looking closely at the code changes to see if they prevent the conditions from occurring that would allow the recursive function to return before calling itself again.
And to help with analysis, you might try adding some "print" statements right before the recursive calls to show which arguments are being passed, and perhaps the current nesting level. One possible "tell" would be if you see the same arguments being passed at different nesting levels.
Kong Tat Ong
5,145 PointsKong Tat Ong
5,145 PointsIt turns out I neglected the
left_end = end // 2
It cannot be end // 2 because you will be splitting the array multiple times which means that the end index will remain the same but the length of the list will change as a result giving a false midpoint. It should be
left_end = (end+start) // 2
Thanks for the help. I think I was just too lazy to study my code step by step; hence, resulting in this.