Sorting II: Merge Sort

What we are trying to do

To sort a list means to rearrange its items into order, usually smallest to largest. The list [5, 2, 4, 1] sorted becomes [1, 2, 4, 5]. Sorting matters because ordered data is easy to search, to compare, and to summarize.

The simple sorting methods you meet first do a lot of repeated scanning. On a list of n items they take on the order of n * n operations (written O(n^2)). Here n is the size of the input, the number of items in the list, and an operation is one small unit of work such as comparing two numbers. When n is 1,000, n * n is a million steps. When n is a million, it is a trillion. That grows too fast to be usable on large data.

Merge sort is a faster method. It takes on the order of n * log n operations, which for a million items is around twenty million steps instead of a trillion. This lesson explains how it works and walks through it step by step.

Two words we will lean on:

• Divide and conquer: a problem-solving pattern where you split a problem into smaller problems of the same kind, solve those, and combine their answers.
• Recursion: a function that calls itself on a smaller version of its input. If that idea is new, the short version is: a function is allowed to invoke itself, and as long as each call works on a smaller piece and there is a smallest piece that needs no further work, the calls eventually stop.

The idea in three steps

Merge sort is built entirely on this observation: it is easy to combine two already-sorted lists into one sorted list. Given that, sorting the whole thing becomes three steps.

1. Divide. Split the list into two halves.
2. Conquer. Sort each half. (Do this by applying the same three steps to each half. That is the recursion.)
3. Combine. Merge the two sorted halves into one sorted list.

The recursion needs a stopping point, called the base case: a list of length 0 or 1 is already sorted, so there is nothing to do. Every split makes the pieces smaller, so we always reach that base case.

Here is the overall shape for the list [5, 2, 4, 1, 3, 6]. Reading top to bottom shows the splits; reading bottom to top shows the merges that rebuild a sorted list.

flowchart TD
    A["[5, 2, 4, 1, 3, 6]"] --> B["[5, 2, 4]"]
    A --> C["[1, 3, 6]"]
    B --> D["[5]"]
    B --> E["[2, 4]"]
    E --> F["[2]"]
    E --> G["[4]"]
    C --> H["[1]"]
    C --> I["[3, 6]"]
    I --> J["[3]"]
    I --> K["[6]"]

    F -. merge .-> L["[2, 4]"]
    G -. merge .-> L
    D -. merge .-> M["[2, 4, 5]"]
    L -. merge .-> M
    J -. merge .-> N["[3, 6]"]
    K -. merge .-> N
    H -. merge .-> O["[1, 3, 6]"]
    N -. merge .-> O
    M -. merge .-> P["[1, 2, 3, 4, 5, 6]"]
    O -. merge .-> P

The solid arrows going down are the splitting. The dotted arrows coming back up are the merging. Single-item lists at the bottom are already sorted, so the real work is all in the merges.

The merge step in detail

Everything depends on the merge, so we build that first. The input is two lists that are each already sorted. The output is one sorted list containing every item from both.

The method: put a finger at the start of each list. Compare the two items your fingers point at, take the smaller one, and move that finger forward. Repeat until one list runs out, then append whatever is left in the other list (it is already sorted, so it goes on as-is).

def merge(left, right):
    result = []
    i = 0                    # finger into left
    j = 0                    # finger into right
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # one side is now empty; attach the rest of the other
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge([2, 4, 5], [1, 3, 6]))   # -> [1, 2, 3, 4, 5, 6]

A few terms in that code: append adds one item to the end of a list; extend adds every item from another list to the end; left[i:] is a slice, meaning “all items from index i onward” (indexing starts at 0, so index 0 is the first item). The while loop keeps running as long as both fingers are still inside their lists.

Tracing one merge, step by step

Merge left = [2, 4, 5] and right = [1, 3, 6], recording the full state after each comparison. i and j are the finger positions; result is what we have committed so far.

At each step we compared exactly one pair, took the smaller, and advanced that finger. When i hit the end of left, the loop stopped and the leftover [6] was attached in one move.

Cost of one merge: each item from either list is looked at and placed exactly once. If the two lists together hold k items, the merge does about k operations. That is O(k) time. It also builds a new result list of size k, so it uses O(k) extra space.

The full algorithm

With merge in hand, merge sort itself is short. Split, sort each half by calling itself, merge the results.

def merge_sort(items):
    if len(items) <= 1:          # base case: already sorted
        return items
    mid = len(items) // 2        # // is integer division: 5 // 2 -> 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)

print(merge_sort([5, 2, 4, 1, 3, 6]))   # -> [1, 2, 3, 4, 5, 6]
print(merge_sort([]))                    # -> []
print(merge_sort([42]))                  # -> [42]

Note // is integer division: it divides and throws away any remainder, so 5 // 2 is 2, not 2.5. We need a whole number to split at. items[:mid] is the slice up to (but not including) mid; items[mid:] is the rest. Together they cover the whole list with no overlap.

This version returns a brand-new sorted list and leaves the original untouched, which is easy to reason about.

Why it costs O(n log n) time

Look again at the tree diagram, but think of it in levels.

• At the top level there is one list of size n.
• The next level down has two lists whose sizes add up to n.
• The next has four lists that still add up to n. And so on.

At every level, the pieces together contain all n items, and merging that whole level costs about n operations total (each item is touched once during that level’s merges). So the cost is n per level.

How many levels are there? Each level halves the piece size: n, then n/2, then n/4, down to size 1. The number of times you can halve n before reaching 1 is log n (the base-2 logarithm). For n = 8 that is 3 halvings; for n = 1,000,000 it is about 20.

Multiply the two: n work per level times log n levels gives O(n log n) time. This holds in the best, average, and worst case, because merge sort always splits down the middle and always does the full merges regardless of how the input is arranged.

A concrete sense of why this wins:

Why it costs O(n) space

Space complexity measures extra memory used beyond the input, as a function of n. Each merge builds a new result list. The largest single merge, at the top, produces a list of size n, so at least O(n) extra memory is in use.

There is also memory used by the recursion itself. Each active function call takes a little stack space, and the calls nest log n deep, which is O(log n). Since n is larger than log n, the total extra space is dominated by the merge buffers: O(n) space. This is the main tradeoff of merge sort. It is fast and predictable, but unlike some sorts it does not sort “in place”; it needs room for a copy.

Stability

A sort is stable if items that compare as equal keep their original relative order. This matters when items carry more than the key you sort on. Suppose you sort a list of (name, score) pairs by score; a stable sort guarantees two people with the same score stay in the order they came in.

Merge sort is stable, and the reason is one character in the merge: the comparison left[i] <= right[j]. When the two fingers point at equal values, we take from left first. Since left holds the items that came earlier in the original list, equal items keep their original order. If you changed <= to <, you would take from the right first on ties and break stability.

pairs = [("ann", 2), ("ben", 1), ("cara", 2), ("dan", 1)]
# sort by the score (the second element of each pair)
by_score = sorted(pairs, key=lambda p: p[1])
print(by_score)
# -> [('ben', 1), ('dan', 1), ('ann', 2), ('cara', 2)]

Python’s built-in sorted is stable, so ben stays before dan and ann stays before cara. A correctly written merge sort gives the same guarantee.

Common pitfalls

• Forgetting the base case. If you drop the if len(items) <= 1 check, the function keeps splitting a one-item list forever and the program crashes with a recursion error. Every recursion needs a smallest case that returns without calling itself.
• Splitting off by one. The two slices must together cover the whole list exactly once. items[:mid] and items[mid:] do this correctly. If you wrote items[mid+1:] you would silently drop the middle item.
• Using / instead of // for the midpoint. In Python / gives a float (5 / 2 is 2.5), and a slice index must be a whole number. Use //.
• Assuming it sorts in place. Merge sort needs O(n) extra memory. If you are on a tiny device with almost no spare memory, an in-place sort may fit better even if it is otherwise similar in speed.
• Breaking stability with <. Keep the tie-break as <= (take from the left on equal values) if you care about preserving original order.
• Comparing incompatible types. Merge relies on <=. Sorting a list that mixes numbers and strings raises a TypeError, because Python will not compare them.

Practice

1. Add a print inside merge that shows left, right, and the returned result each time it runs. Sort [3, 1, 2, 5, 4] and read the output from the smallest merges up to the final one. Check that it matches the tree structure in this lesson.
2. Write a version of merge that merges into descending order (largest first) and confirm merge_sort built on it sorts a list from high to low.
3. Modify merge to also return a count of how many comparisons it made. Sum the counts across a full merge_sort of a list of 8 items, and compare the total to n * log n = 8 * 3 = 24.