Merging two sorted lists is a small algorithm with several obligations: it must put values in order, preserve every node exactly once, and end the result at null.
1. A stable destructive merge
Definition 18.1.1
(Stable destructive merge)
Assume two disjoint, finite, acyclic singly linked lists sorted in nondecreasing key order. Each node contains a key and next. The merge may relink the input nodes: callers must not use their old list heads as independent lists afterwards. Equal keys may belong to distinct nodes. To make the merge stable, when the front keys are equal choose the node from the left list first; do not otherwise change the order inside either input list.
merge(left, right):
dummy.next = null
tail = dummy
while left != null and right != null:
if left.key <= right.key:
chosen = left; left = left.next
else:
chosen = right; right = right.next
tail.next = chosen
tail = chosen
if left != null: tail.next = left
else: tail.next = right
return dummy.next
The dummy is a temporary sentinel, not an output data node. Save the successor by advancing the relevant input pointer before a later iteration overwrites any link. The old tail.next can still point into an input suffix until the next assignment, so during the loop the output is read only up to tail; it is not yet an independent null-terminated list.
Theorem 18.1.2
(Correctness and cost of the destructive merge)
Let left and right be disjoint, finite, acyclic singly linked lists of and nodes, each sorted in nondecreasing key order. Then merge(left, right) returns a null-terminated list that contains every node of both inputs exactly once and is sorted in nondecreasing key order. The nodes of each input keep their input order, and every left node precedes every right node of equal key. The merge makes at most key comparisons when and none otherwise, and takes time and auxiliary pointer space, excluding the input nodes.
Proof
(An invariant about the output prefix and the two suffixes)
Call the nodes moved so far the selected nodes. At each test of the loop condition, the following hold. (i) Following next from dummy up to tail visits exactly the selected nodes, in the order they were selected. (ii) The keys along this prefix are nondecreasing, and each is no larger than the key of every non-null remaining head. (iii) left and right point to the untouched suffixes of the two inputs, which are still disjoint and still sorted.
Initially nothing is selected, tail is dummy, and the suffixes are the whole inputs. Suppose the loop body runs. Because each suffix is sorted, the smaller of the two heads is no larger than every remaining key in both suffixes. Whichever head is chosen, it is that smaller head (with ties going left), so appending it keeps (ii). The chosen input pointer advances first, so the rest of that suffix is not lost when tail.next is overwritten in the next iteration; (i) and (iii) are preserved.
The loop ends when one input pointer is null. Each iteration removed one node, and the other list was nonempty during the iteration, so at least one node remains in the other suffix. That suffix is sorted, its keys are at least every key in the prefix by (ii), and it ends in null because the input is finite and acyclic. A single assignment attaches it, so the result is null-terminated and every node appears once, since nodes were moved one at a time out of disjoint lists. Nodes of one input are taken from the front, so each input keeps its order.
For stability, a right head is chosen over the left head only when strictly. The left suffix is sorted, so no remaining left node then has the right node's key. Hence each left node of key is selected before any right node of key .
There are at most iterations when , and each does work, as does the final attachment. The extra storage is dummy, tail, chosen, which is .
Proof X-ray
The invariant has to describe links, not just keys
The invariant talks about three things at once: the keys of the output prefix, the identity of its nodes, and the state of the two input suffixes. Each hypothesis is used in one place. Sortedness of the inputs is used once, to know that the smaller head is smaller than everything remaining in its own list. Disjointness is used for the claim that every iteration removes a node from exactly one suffix and leaves the suffixes disjoint. Finiteness and acyclicity are used only at the end, to know that the attached suffix terminates in null.
The one delicate point is the overwrite. In the next iteration tail.next is assigned, replacing the pointer that used to lead to the rest of the chosen node's list. That is harmless because the input pointer was advanced in the same iteration, which saved the successor.
The argument closes when one head is null: the invariant already says the prefix is sorted and below everything left, so the remaining suffix can be attached wholesale without further comparison.
The remaining parts of the hypotheses are easy to violate in practice.
Counterexample mode
Shared nodes make the merge create a cycle
Suppose left is 1a -> x and right is 2c -> x, where x is one node with key 5 and x.next is null. The lists share the node x. The loop selects 1a (since ) and then 2c (since ), after which both left and right equal x. Now , so chosen = x, left = x.next = null, tail.next = x, and the loop ends. The final branch sets tail.next = right, which is x, so x.next = x. The output is 1a -> 2c -> x -> x -> ..., which never reaches null.
The failure comes from the hypothesis that the input lists are disjoint: a shared node is selected once from each side, and the second selection relinks it to itself. The repair is the precondition itself, not a patch to the loop.
Common mistake
(Using a strict comparison in the merge)
If the loop tests left.key < right.key instead of left.key <= right.key, equal keys are taken from the right list first. For left 2a and right 2c, the output is 2c -> 2a. Sortedness is unchanged, but the sort is no longer stable.
Worked example 18.1.3
(A merge with ties across the two lists)
Let the left list be 1a -> 3a -> 3b and the right list 2c -> 3c -> 5c, where letters identify nodes. Select 1a (1 against 2), then 2c (3 against 2). Next the heads are 3a and 3c, equal keys, so the left node 3a is selected; then 3b against 3c is again a tie, so 3b is selected. The left list is now empty, so the remaining 3c -> 5c is appended without further comparisons. The final chain is 1a -> 2c -> 3a -> 3b -> 3c -> 5c -> null. There were 4 comparisons, at most .
Values sort correctly, all six identities occur once, and equal keys retain left-before-right order. Stability says more than simply returning the sequence of key values.
2. Splitting and sorting
Definition 18.1.4
(Slow and fast pointer split)
A linked-list merge sort splits a list of nodes into two shorter contiguous lists, sorts each recursively, then merges them. The split uses a slow pointer starting at the head and a fast pointer starting at the second node. While fast and fast.next are non-null, advance slow once and fast twice. Save right = slow.next, then set slow.next = null. The left half runs from the original head to slow, and the right half starts at right. Empty and singleton lists are base cases.
Theorem 18.1.5
(Splitting, correctness and cost of linked-list merge sort)
For , the split produces two disjoint null-terminated lists with and nodes, in original order and together containing every node once. Linked-list merge sort returns the same nodes sorted in nondecreasing key order and stably. It takes time and recursion stack, and reuses the list nodes.
Proof
(Counting pointer steps, then induction on the length)
Number the nodes . After iterations of the loop, slow is at position and fast at position , where a position beyond means null. The loop runs again exactly when fast and fast.next exist, that is, when . It therefore stops after iterations, with slow at position . Cutting after slow leaves a left list of nodes and a right list of nodes, since . Both are strictly shorter than .
Induct on the length. Lists of length at most one are sorted. For , the halves are shorter, disjoint, finite and acyclic, so by hypothesis the recursive calls return sorted lists consisting of exactly their own nodes. The merge theorem applies and gives a sorted list of all nodes.
For stability, take equal-key nodes before in the input. If both lie in one half, the recursive call and then the merge keep their order. Otherwise is in the left half and in the right, and the merge puts left before right.
For the cost, at recursion depth the sublists partition the nodes, and each has at most nodes. Splitting a list of nodes takes about steps and merging takes , so one depth costs . The sublists have one node when , so there are depths and time. The recursion stack holds one frame per depth, which is .
Concept lensStructural
Stability as an order on key and position
Number the nodes in input order. A stable sort returns the nodes exactly in increasing order of the pairs , compared lexicographically. These pairs are all distinct, so that order is unique. For 4a -> 1b -> 3c -> 2d the pairs are , and sorting them gives 1b, 2d, 3c, 4a. Preferring the left node on ties is how each merge respects the position component.
Worked example 18.1.6
(Splitting and sorting four nodes)
For 4a -> 1b -> 3c -> 2d, the split gives [4a,1b] and [3c,2d]. Sorting the halves gives [1b,4a] and [2d,3c]; merging compares 1 with 2 (take 1b), 4 with 2 (take 2d), 4 with 3 (take 3c), and appends 4a, giving [1b,2d,3c,4a]. Termination follows from smaller sublists. Inductively, each returned half is sorted and contains exactly its original nodes; the merge argument then supplies the result for the whole list. Since the split keeps contiguous input order and equality is resolved in favor of the left half, the complete sort is stable.
Worked example 18.1.7
(Edge cases: empty inputs and an odd length)
If left is null and right is 2a -> 4a, the loop body does not run. Because left is null, the final branch sets tail.next = right, and the function returns dummy.next, which is 2a. If both inputs are null, the same branch sets dummy.next to null and the result is null.
Now split 5a -> 4b -> 3c -> 2d -> 1e. The slow pointer starts at 5a and the fast pointer at 4b. Both fast and fast.next exist, so slow moves to 4b and fast to 2d. Again both exist (2d and 1e), so slow moves to 3c and fast moves two nodes to null. The loop stops. Saving right = 2d and cutting 3c.next gives 5a -> 4b -> 3c and 2d -> 1e, with sizes and , as the theorem predicts. Saving right before cutting matters, as the next block shows.
Common mistake
(Cutting the list before saving the right half)
If the split sets slow.next = null first and then reads right = slow.next, it reads null. For 4a -> 1b -> 3c -> 2d, the slow pointer ends at 1b; cutting first makes right null, and the nodes 3c and 2d are lost.
The merge itself uses constant auxiliary pointers, so the stack bound above is the recursion of the sort alone. A different implementation that recursively merges one node per call can require O(n) merge stack depth, so its space claim must be analyzed separately.
3. Exercises with solutions
Quick check
(Merge the left list 2a -> 2b with the right list 2c. Give the result and the number of key comparisons.)
Resolve each tie in favor of the left list.
Solution · Answer
The heads 2a and 2c tie, so 2a is selected. Then 2b against 2c ties again, so 2b is selected. The left list is empty, and 2c is appended. The result is 2a -> 2b -> 2c, after 2 comparisons.
Quick check
(Merging 1a -> 3a -> 5a with 2b -> 4b makes how many key comparisons? What is the largest possible number for lists of lengths 3 and 2?)
Count the iterations until one list is empty.
Solution · Answer
The comparisons are 1 with 2, 3 with 2, 3 with 4, and 5 with 4, so there are 4, after which the right list is empty and 5a is appended. The general bound is , so this input attains the maximum.
Quick check
(Split a list of six nodes n1 -> n2 -> n3 -> n4 -> n5 -> n6 with the slow and fast pointers. Which nodes does each half contain?)
Track the positions of slow and fast until the loop condition fails.
Solution · Answer
Slow starts at n1 and fast at n2. Both fast and fast.next exist, so slow moves to n2 and fast to n4. They exist again, so slow moves to n3 and fast to n6. Now fast.next is null, so the loop stops. The right half starts at n4, so the halves are n1 -> n2 -> n3 and n4 -> n5 -> n6, each of size .
Quick check
(Why must the split cut the list at slow, rather than only recording right = slow.next?)
Ask whether the recursive call on the left half would still see a shorter list.
Solution · Answer
Without the cut, the left half still links into the right half, so the two lists are not disjoint and the left list is not shorter. For a list of two nodes, the left call would receive both nodes again, and the recursion would never reach a base case.