 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 < right:
result.append(left)
left.pop(0)
else:
result.append(right)
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 is`left_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 < right:
result.append(left.pop(0))
else:
result.append(right.pop(0))
``````
2 Likes