Help Please

A question on a quiz asked which value in [12, 13, 14, 15] is the first assigned to right sorted. Apparently the answer was 13, I thought is was 14. Could you explain how?

def merge_sort(items):
  if len(items) <= 1:
    return items

  middle_index = len(items) // 2
  left_split = items[:middle_index]
  right_split = items[middle_index:]
	
  left_sorted = merge_sort(left_split)
  right_sorted = merge_sort(right_split)
  
  return merge(left_sorted, right_sorted)

def merge(left, right):
  result = []

  while (left and right):
    if left[0] < right[0]:
      result.append(left[0])
      left.pop(0)
    else:
      result.append(right[0])
      right.pop(0)
  
  if left:
    result += left
  if right:
    result += right
  
  return result

The first recursive step encountered,left_sorted = merge_sort(left_split), must run “all the way down” before the second one is encountered.

left_split is originally [12, 13], and right_split is [14, 15]

The next step isleft_sorted = merge_sort(left_split),
… which takes us back into the function, with items = [12, 13].

So left_split becomes 12 and right_split 13

And, again,left_split = merge_sort(left_split) this time returns 12 since len(items) is now 1

OK, now we’re done with left_sorted, so moving back up the stack, this is the first time we’ve encountered right_sorted , where we have right_sorted = merge_sort(right_split), and right_split is 13, the right side of that [12, 13] at the top; it will return 13.

2 Likes

Just a quick note on pop

list.pop() returns the value so those lines can be written,

    if left[0] < right[0]:
      result.append(left.pop(0))      
    else:
      result.append(right.pop(0))      
2 Likes