Two teachers must put 200 exam papers in order by name. Each teacher takes 100 and sorts them.

Now they have two sorted piles. They put them side by side. They look at the top paper of each pile and take the one that comes first. They do this again and again, until one sorted pile is left.

A computer does the same, but it splits much further: until each pile has one item. This method has a name: merge sort means split, then merge.

To merge two sorted lists, look at the front item of each. Take the smaller one. Do it again with the new fronts.

You never need to look further back. This is quick, because both lists are already in order.

left = [3, 5]
right = [1, 8]
result = []

while len(left) > 0 and len(right) > 0:
    if left[0] <= right[0]:
        result.append(left.pop(0))
    else:
        result.append(right.pop(0))
    print("Result so far:", result)

result = result + left + right
print("Merged:", result)

# pop(0) takes the front item out of a list.
# Change the two lists. Keep each one sorted.

Merge sort splits a list until every part has one item. A part with one item is already sorted.

Then it merges. First it merges parts of 1 into parts of 2. Then parts of 2 into parts of 4. Each round uses the same merge you just did. Look at the picture again to follow it.