Welcome to the Treehouse Community

The Treehouse Community is a meeting place for developers, designers, and programmers of all backgrounds and skill levels to get support. Collaborate here on code errors or bugs that you need feedback on, or asking for an extra set of eyes on your latest project. Join thousands of Treehouse students and alumni in the community today. (Note: Only Treehouse students can comment or ask questions, but non-students are welcome to browse our conversations.)

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and a supportive community. Start your free trial today.

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
217,531 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.