Sort Linked List, in depth: merge sort on a singly linked list, top-down and bottom-up, with the bugs that break it

Why linked lists change the choice of sort

Compare what each classic O(n log n) sort needs from its container:

Merge sort only ever walks forward and compares adjacent heads, which is exactly what a linked list does well. It is also stable: equal keys keep their original order, provided the merge takes from the left list on ties. Stability matters when you sort records by one key after sorting them by another, for example orders by date and then by customer.

The plan: split, sort, merge

The top-down algorithm has three steps. Split the list into two halves by finding the middle and cutting the link after it. Sort each half recursively; a list of zero or one node is already sorted. Merge the two sorted halves by repeatedly detaching the smaller head and appending it to an output chain. Each level of recursion touches every node a constant number of times, and there are about log₂ n levels, so the running time is O(n log n) in the best, average and worst case alike.

Splitting at the middle without an infinite loop

Without a length field you find the middle with two pointers: slow advances one node per step, fast advances two, and when fast runs off the end slow is at the middle. The detail that matters is where fast starts. If both start at the head, then on a two-node list slow ends on the second node, the cut after it produces halves of size two and zero, and the recursion calls itself on the same two-node list forever. Starting fast one node ahead makes slow stop on the last node of the left half, so every split shrinks both sides. The same pattern is covered in detail in finding the middle of a linked list.

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

def split_middle(head):
    """Cut a list of at least 2 nodes into two non-empty halves; return the second."""
    slow, fast = head, head.next          # fast starts one ahead: avoids the 2-node loop
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    second = slow.next
    slow.next = None                      # the cut: without it the halves stay joined
    return second

For a list of n nodes the left half gets the ceiling of n/2 nodes and the right half the floor. With 5 nodes, slow stops on node 3 and the halves are 3 and 2; with 2 nodes it stops on node 1 and the halves are 1 and 1.

A stable, iterative merge

The merge uses a dummy node so the first append is not a special case. It is iterative on purpose. The elegant recursive merge has recursion depth equal to the combined length of the two lists, so merging two 600-node lists already exceeds Python's default recursion limit of 1,000, and on the JVM a long list can overflow the thread stack.

def merge(a, b):
    dummy = tail = Node(None)
    while a is not None and b is not None:
        if a.val <= b.val:                # <= takes from the left on ties: keeps the sort 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 # append the remainder in one link
    return dummy.next

def sort_list(head):
    if head is None or head.next is None:
        return head
    second = split_middle(head)
    return merge(sort_list(head), sort_list(second))

The recursion in sort_list is only about log₂ n deep, about 20 levels for a million nodes and 30 for a billion, so it is safe in any language. The total cost is n log n comparisons at most and the same order of pointer writes. Memory beyond the list itself is the O(log n) call stack and one dummy node per merge.

Bottom-up merge sort in constant extra space

If even logarithmic stack is unacceptable, for example in an interrupt handler, a kernel or an interview asking for O(1) extra space, sort bottom-up. Count the length once, then make passes that merge adjacent runs of size 1, then 2, then 4, until one run covers the list. Each pass walks the list, cuts off two runs, merges them and links the result to the tail of what has been built so far.

def cut(head, size):
    """Detach the first `size` nodes; return the head of what follows."""
    for _ in range(size - 1):
        if head is None:
            return None
        head = head.next
    if head is None:
        return None
    rest, head.next = head.next, None
    return rest

def sort_list_bottom_up(head):
    n, node = 0, head
    while node is not None:
        n, node = n + 1, node.next
    dummy = Node(None, head)
    size = 1
    while size < n:
        prev, cur = dummy, dummy.next
        while cur is not None:
            left = cur
            right = cut(left, size)       # left now holds at most `size` nodes
            cur = cut(right, size)        # right holds at most `size`; cur is the remainder
            prev.next = merge(left, right)
            while prev.next is not None:  # advance to the tail of the merged run
                prev = prev.next
        size *= 2
    return dummy.next

This version uses a handful of pointers regardless of n. Walking to the tail of each merged run adds work, but every node is walked a constant number of times per pass, so the total stays O(n log n). A refinement has merge return its tail to avoid the extra walk. The kernel's list_sort goes further, merging runs as they arrive to keep them balanced and cache-friendly, but the idea is the same.

Worked example: tracing the passes

Trace the bottom-up version on 4 → 2 → 1 → 3 → 5, where n = 5.

1. size = 1. Cut [4] and [2], merge to 2 → 4. Cut [1] and [3], merge to 1 → 3. Cut [5] and an empty run, merge to 5. The list is now 2 → 4 → 1 → 3 → 5.
2. size = 2. Cut [2, 4] and [1, 3]. Merge: compare 2 and 1, take 1; compare 2 and 3, take 2; compare 4 and 3, take 3; the right side is empty, so link 4. Result 1 → 2 → 3 → 4. Then cut [5] with an empty partner. The list is 1 → 2 → 3 → 4 → 5.
3. size = 4. Cut [1, 2, 3, 4] and [5]. Merge: 1, 2, 3 and 4 each win a comparison against 5, four comparisons in all, then 5 is linked as the remainder. Done.
4. size = 8 is not less than 5, so the loop ends.

Three passes for five nodes, matching the ceiling of log₂ 5. Count the comparisons: 2 in the first pass, 3 in the second and 4 in the third, 9 in total, comfortably under the n log n bound of about 11.6.

Failure modes

• Infinite recursion on two nodes. Starting fast at the head instead of head.next. Always test lengths 0, 1, 2 and 3 explicitly.
• Forgetting the cut. Omitting slow.next = None leaves the left half attached to the right, so the recursion sees the whole list again.
• Lost nodes. Dropping the remainder after the merge loop, or returning dummy instead of dummy.next. Assert that the output length equals the input length.
• Accidental cycles. In the bottom-up version, failing to terminate a cut run lets a merged run point back into unsorted territory. A Floyd cycle check in tests catches this quickly.
• Broken stability. Using < instead of <= in the merge takes equal keys from the right first. Results still look sorted, which is why only a test with duplicate keys and payloads reveals it.
• Recursive merge on long lists. A RecursionError in Python or StackOverflowError in Java once lists reach a few thousand nodes.
• Comparing incomparable keys. Mixing None or different types in Python raises TypeError in the middle of a merge, leaving the list half relinked. Validate or use a key function first.

Testing it properly

A property-based test catches every bug in the list above in a few lines: generate random lists including duplicates, sort them with the linked-list code and with the language's built-in stable sort on (key, original position) pairs, and compare both values and order.

import random

class Rec:
    """A record that compares by key only, so equal keys are genuine ties."""
    __slots__ = ("key", "pos")
    def __init__(self, key, pos):
        self.key, self.pos = key, pos
    def __le__(self, other):
        return self.key <= other.key

def to_list(vals):
    head = None
    for v in reversed(vals):
        head = Node(v, head)
    return head

def to_py(head, limit=10**6):
    out = []
    while head is not None and len(out) <= limit:   # limit guards against cycles
        out.append((head.val.key, head.val.pos))
        head = head.next
    return out

for trial in range(2000):
    n = random.randint(0, 40)
    xs = [(random.randint(0, 5), i) for i in range(n)]   # (key, original position)
    want = sorted(xs, key=lambda t: t[0])                # Python's sort is stable
    for fn in (sort_list, sort_list_bottom_up):
        got = to_py(fn(to_list([Rec(k, i) for k, i in xs])))
        assert got == want, (fn.__name__, xs)            # same keys AND same tie order

Keys are drawn from only six values, so most lists contain many ties, and Rec compares keys alone, so the merge cannot break a tie by position. If the output order of equal keys differs from Python's stable sorted, the merge is unstable. The length check is implicit in the list comparison, and the limit in to_py turns a cycle into a failed assertion instead of a hang.

In practice: cache behaviour and alternatives

Asymptotics are not the whole story. Each node visit is a pointer dereference to wherever the allocator put that node, so linked-list sorts suffer cache misses that array sorts avoid. When extra memory is available, copying the values into an array, sorting the array and writing the values back, or relinking the nodes in sorted order, is often faster in practice. Java's List.sort default implementation does exactly this: it dumps the elements to an array, sorts that, and writes them back through a list iterator. Choose in-place list merge sort when nodes are large or not movable, when you must not allocate, or when other structures hold pointers to the nodes and those must stay valid.

The building blocks reuse well. The merge step is the core of merging k sorted lists, and the pointer discipline is the same as in iterative list reversal and the basic singly linked list operations.

What to do next

1. Implement split_middle with fast = head.next and test it on lists of length 0 to 5.
2. Write the iterative merge with a dummy node and <= for stability.
3. Combine them into the top-down sort_list and run the property test above.
4. Implement the bottom-up version with cut and confirm it uses no recursion at all.
5. Add assertions for output length and a cycle check to your test harness.
6. Benchmark against copy-to-array, sort and relink on a million nodes in your language, and pick based on measured time and memory limits.
7. Practise the same split-and-merge pointer moves on related problems: merge k sorted lists and reorder list.