Skip to the content
Start

Merge sort

Python · Unit 23: Searching and sorting

Merging two lists that already come sorted is easy: you look at the first one of each, take the smaller one and carry on.

When one of them runs out, whatever is left of the other is already in order and gets tacked on at the end.

def merge(a, b):
    r = []
    while len(a) > 0 and len(b) > 0:
        if a[0] <= b[0]:
            r.append(a.pop(0))
        else:
            r.append(b.pop(0))
    return r + a + b

print(merge([2, 5, 9], [1, 6]))

Prints

[1, 2, 5, 6, 9]

The rest of the explanation is in the lesson, which is part of the full plan.

Exercises in this lesson

You do them in the app, which checks them on the spot and explains why.

  1. 1. Predict the output

    What does this code print?

  2. 2. Complete the code

    The while ends when one of the two lists runs out. What is left to return?

  3. 3. Find the bug

    merge should join the two sorted lists and give [1, 2, 5, 6, 9], but it prints [2, 5, 9, 1, 6]. Which line has the error?

  4. 4. Predict the output

    What does this code print?

  5. 5. Predict the output

    This function cuts and cuts again until a single number is left. What does it print?

  6. 6. Complete the code

    Complete the call that sorts the second half.

  7. 7. Multiple choice

    What is the if len(ns) <= 1: return ns in merge sort for?

  8. 8. Find the case that fails

    merge(a, b) should return the numbers of both sorted lists in a single one, including when one of them arrives empty. Which call breaks it?

Do this lesson

It opens in your browser. This lesson is part of the full plan; the first unit of each course is free.

See all lessons →