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

Computer Science Introduction to Data Structures The Merge Sort Algorithm Evaluating the Runtime of Merge Sort

Kong Tat Ong
Kong Tat Ong
5,145 Points

What 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
Steven Parker
229,732 Points

I'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
Kong Tat Ong
5,145 Points

It 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.