Merge Two Sorted Lists, in Depth

The problem, precisely

You are given the heads of two singly linked lists, a and b, each sorted in non-decreasing order by some key. Return the head of one list that contains every node of both inputs, sorted in non-decreasing order. The usual node shape is a value and a next pointer.

Four properties make up the full contract, and most bugs violate one of them silently:

1. Permutation. The output contains exactly the input nodes: none lost, none duplicated, no new nodes allocated. The merge re-links; it does not copy.
2. Order. For consecutive output nodes x and y, x.key <= y.key.
3. Stability. If two nodes have equal keys, a node from a comes before a node from b, and nodes from the same input keep their original order. Merge sort is stable only because its merge is.
4. Termination. The output ends in None with no cycle, and the inputs are consumed: the caller must not use a or b as lists afterwards.

The invariant that writes the code

The algorithm follows from one invariant. Keep a pointer tail to the last node of the output built so far. At the top of every loop iteration:

• the output, from the dummy's successor to tail, is sorted and stable;
• every node in that output is less than or equal to every node still in a and b;
• a and b point to the unconsumed suffixes of the inputs, each still sorted.

To extend the output while preserving the invariant you must append the smallest remaining node. Since both remainders are sorted, the smallest remaining node is one of the two heads, so one comparison picks it. When one remainder becomes empty, the other remainder is already sorted and every element in it is at least the current tail, so you attach it in a single pointer assignment and stop. That last step is why the merge often finishes long before it has visited every node.

The dummy head (a sentinel node) exists only to remove a special case. Without it, the first append sets the result head while later appends set tail.next. With a sentinel, every append is tail.next = chosen, and the answer is dummy.next.

The problem, precisely

You are given the heads of two singly linked lists, a and b, each sorted in non-decreasing order by some key. Return the head of one list that contains every node of both inputs, sorted in non-decreasing order. The usual node shape is a value and a next pointer.

Four properties make up the full contract, and most bugs violate one of them silently:

1. Permutation. The output contains exactly the input nodes: none lost, none duplicated, no new nodes allocated. The merge re-links; it does not copy.
2. Order. For consecutive output nodes x and y, x.key <= y.key.
3. Stability. If two nodes have equal keys, a node from a comes before a node from b, and nodes from the same input keep their original order. Merge sort is stable only because its merge is.
4. Termination. The output ends in None with no cycle, and the inputs are consumed: the caller must not use a or b as lists afterwards.

The invariant that writes the code

The algorithm follows from one invariant. Keep a pointer tail to the last node of the output built so far. At the top of every loop iteration:

• the output, from the dummy's successor to tail, is sorted and stable;
• every node in that output is less than or equal to every node still in a and b;
• a and b point to the unconsumed suffixes of the inputs, each still sorted.

To extend the output while preserving the invariant you must append the smallest remaining node. Since both remainders are sorted, the smallest remaining node is one of the two heads, so one comparison picks it. When one remainder becomes empty, the other remainder is already sorted and every element in it is at least the current tail, so you attach it in a single pointer assignment and stop. That last step is why the merge often finishes long before it has visited every node.

The dummy head (a sentinel node) exists only to remove a special case. Without it, the first append sets the result head while later appends set tail.next. With a sentinel, every append is tail.next = chosen, and the answer is dummy.next.

Iterative implementation

Here is the iterative merge in Python. The comparison uses <= so that ties go to a; the next section explains why that character matters.

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next


def merge(a, b, key=lambda node: node.val):
    """Splice two sorted lists into one. Stable: ties take from `a` first.
    O(m + n) time, O(1) extra space, allocates only the sentinel."""
    if a is b and a is not None:
        raise ValueError("cannot merge a list with itself")
    dummy = Node(None)
    tail = dummy
    while a is not None and b is not None:
        if key(a) <= key(b):        # '<=' keeps the merge stable
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a if a is not None else b   # attach the leftover run
    return dummy.next

The loop does one comparison and three pointer writes per appended node and never touches the leftover run. In C the sentinel is often replaced by a pointer to a pointer that always addresses the field due to receive the next node, first the head variable and then the last node's next; it saves the dummy but is harder to read.

Stability lives in one character

Change <= to < and the output is still sorted, every unit test that checks sortedness still passes, and the merge is no longer stable: on a tie it now takes from b first. For records sorted by one field, that is a correctness bug.

Suppose orders are sorted by timestamp, and a merge sort on linked lists sorts them again by customer id. Users expect each customer's orders to stay in time order, because that is what a stable sort promises. Merge sort splits the list into a left half and a right half and merges them back, with the left half passed as a. With <=, equal customer ids keep their left-before-right order at every level, so time order survives. With <, every tie flips at every merge level, and the final order of one customer's orders depends on how the recursion happened to split them.

So the argument order is part of the API: document that a wins ties, pass the earlier run as a, and test with duplicate keys that carry a payload, since distinct keys cannot reveal instability.

Why not to ship the recursive version

The recursive version is the one most textbooks show, and it is genuinely elegant:

def merge_rec(a, b):
    if a is None:
        return b
    if b is None:
        return a
    if a.val <= b.val:
        a.next = merge_rec(a.next, b)
        return a
    b.next = merge_rec(a, b.next)
    return b

Its problem is depth. Each appended node costs one stack frame, so merging lists with m and n nodes can need up to m + n frames before the leftover run ends the recursion. CPython's default recursion limit, reported by sys.getrecursionlimit(), is 1000, so this function raises RecursionError on two lists of about 500 nodes each. Raising the limit trades the exception for O(m + n) frame memory on CPython 3.11 and later; older interpreters, and recursion through C code, can still overflow the native stack. In C, Java or Go the limit is larger but still proportional to input size, and a stack overflow from a list that arrived over the network is a denial of service bug.

It is not tail recursive either, since the assignment to a.next follows the call, so tail-call elimination cannot save it. Ship the loop.

Worked example

Merge a = 1 -> 4 -> 4 -> 9 and b = 2 -> 4 -> 7. To make stability visible, call the nodes of a by their values with a subscript of a, so a holds 1a, 4a, 4a' and 9a, and b holds 2b, 4b and 7b.

Six comparisons for seven nodes, which is the worst case of m + n - 1. Steps 3 and 4 are the stability test: both 4s from a precede the 4 from b, in their original order. With < instead, step 3 would append 4b first. The final step costs nothing: the loop ends when b is exhausted and the leftover run (just 9a here, but it could be a million nodes) is attached with one assignment.

Cost, precisely

Time is linear, but the precise counts are worth knowing because they explain the behaviour of everything built on top of the merge.

• Comparisons: at most m + n - 1, when the two lists interleave until the very end, and at least min(m, n), when every element of the shorter list is smaller than the first element of the longer one. Merge sort's near-sorted speed-up and the cheapness of appending already-ordered runs both come from that lower bound.
• Extra space: O(1) for the iterative version: two cursors, a tail and a sentinel. The recursive version uses O(m + n) stack.
• Memory traffic: every step chases a pointer to a node anywhere in the heap, so merging cold lists is dominated by cache misses. Array merges stream contiguous memory, which is why large production sorts use arrays.

Beyond linked lists: arrays, iterators and streams

The same two-pointer merge works on anything that can be consumed in order. On arrays the merge cannot splice, so it needs an output buffer of size m + n (or m, if you copy the left run aside and merge back into place, which is what most library merge sorts do). On iterators it becomes a generator that holds one pending element from each side:

def merge_iter(xs, ys, key=lambda v: v):
    """Lazily merge two sorted iterables. Stable; O(1) memory."""
    xs, ys = iter(xs), iter(ys)
    END = object()
    x, y = next(xs, END), next(ys, END)
    while x is not END and y is not END:
        if key(x) <= key(y):
            yield x
            x = next(xs, END)
        else:
            yield y
            y = next(ys, END)
    if x is not END:
        yield x
        yield from xs
    if y is not END:
        yield y
        yield from ys

That generator is the shape of external sorting and of compaction in log-structured storage: each sorted run is a file read sequentially, the merge emits one record at a time, and memory use is independent of the data size. Python's standard library already ships a k-way version as heapq.merge, which uses a heap when there are many inputs and accepts key and reverse arguments. For more than two inputs, merging pairwise in a balanced tree or using a heap both cost O(N log k); folding the lists left to right costs O(N k) and is the usual performance bug in hand-written k-way merges.

Failure modes

These are the failures that show up in code review and incident reports, roughly in order of frequency.

• Unsorted input. The merge trusts its precondition and returns unsorted output without error. Check sortedness at module or stream boundaries.
• Using a stale head. After merged = merge(a, b), the variable a points into the middle of merged. Iterating from it, freeing it, or merging it again corrupts the structure. Reassign or clear the input references at the call site.
• Aliasing. merge(x, x) splices a list into itself and builds a cycle; the Python version above rejects the obvious case. Overlapping lists, where b is a suffix of a, are harder to detect and produce the same corruption.
• Inconsistent comparators. NaN compares false with everything, so nan <= x and x <= nan are both false and the result order depends on where the NaN sits.

Testing a merge properly

A merge has a clean specification, which makes it ideal for property-based testing. Generate random sorted lists with many duplicate keys, tag every node with its origin and position, and check all four contract properties against a trusted oracle: a stable sort of the concatenation.

import random

def build(pairs):
    head = None
    for key, tag in reversed(pairs):
        n = Node(key); n.tag = tag; n.next = head
        head = n
    return head

def to_list(head, limit=10**6):
    out = []
    while head is not None and len(out) < limit:
        out.append((head.val, head.tag)); head = head.next
    assert head is None, "cycle or runaway list"
    return out

for _ in range(10_000):
    xs = sorted(random.choices(range(5), k=random.randint(0, 8)))
    ys = sorted(random.choices(range(5), k=random.randint(0, 8)))
    a = [(k, ("a", i)) for i, k in enumerate(xs)]
    b = [(k, ("b", i)) for i, k in enumerate(ys)]
    want = sorted(a + b, key=lambda kv: kv[0])   # Python's sort is stable
    got = to_list(merge(build(a), build(b)))
    assert got == want, (a, b, got)

Keys drawn from a range of five force ties on almost every iteration, lengths start at zero so empty inputs appear, and the to_list guard turns a cycle into a failure instead of a hang.

Trade-offs

What to do next

Merge is the building block for a family of algorithms on this site. Sorting a linked list with merge sort uses exactly this routine as its combine step, and merging k sorted lists with a heap generalises it to many inputs. For the pointer manipulation underneath, see singly linked list operations, and for the array version and its analysis, merge sort.

1. Write the iterative merge from memory with a dummy head, then again with a pointer to a pointer.
2. Run the property test above against your version, with duplicate-heavy keys and empty inputs.
3. Change <= to < and confirm the test fails; if it does not, your test cannot see stability.
4. Convert your merge to the generator form and use it to merge two sorted files line by line.
5. Build merge sort on lists from your merge and check that it is stable on records with equal keys.