Merge Sort a Linked List

Sort a linked list is the classic place where merge sort shines. You cannot index into a linked list, so the array-friendly sorts (quicksort with random access, heapsort) are awkward — but merge sort only ever walks forward and splices pointers, which is exactly what a linked list is good at.

The slow way first

The obvious idea: collect every value into an array, sort the array, then overwrite the node values. That works and is O(n log n), but it needs O(n) extra space for the array and quietly ignores the structure of the problem.

The question to ask: what sort splices naturally onto a linked list? Merge sort. It never needs random access — it only splits a list in half and merges two sorted lists by re-pointing next links. Both operations are pure pointer walks, so merge sort fits a linked list perfectly and runs in O(n log n).

The idea: split, sort each half, merge

Merge sort is three moves, applied recursively:

1. Split the list into two halves. Find the middle with the slow/fast trick: fast moves two nodes for every one slow moves, so when fast runs off the end, slow sits on the last node of the first half. Cut the link there.
2. Recurse on each half until a half has 0 or 1 nodes — that is the base case, a list that is already sorted.
3. Merge the two sorted halves into one sorted list by repeatedly taking the smaller head and re-pointing next.

The key insight: the recursion does the hard part for free. By the time we call merge, both halves are already sorted, so merging is a simple two-pointer walk.

Walk through it

Step through the animation. First the slow and fast pointers find the middle of 4 -> 2 -> 1 -> 3, and we cut the list into 4 -> 2 and 1 -> 3. Each half sorts itself: the left becomes 2 -> 4, the right stays 1 -> 3. Then the merge takes the smaller head each time — 1, then 2, then 3, then 4 — threading the nodes back together as 1 -> 2 -> 3 -> 4.

Pseudocode

sort(head):
    if list has 0 or 1 node: return head     # already sorted (base case)
    mid = split list in half                  # slow/fast, then cut
    left  = sort(first half)                   # recurse
    right = sort(second half)                  # recurse
    return merge(left, right)                  # combine two sorted lists
 
get_mid(head):
    slow = head, fast = head.next
    while fast and fast.next:                  # fast moves twice as fast
        slow = slow.next
        fast = fast.next.next
    mid = slow.next                            # second half starts here
    slow.next = None                           # cut the list in two
    return mid

The Python solution

def sort_list(head):
    if not head or not head.next:
        return head
    mid = get_mid(head)
    left = sort_list(head)
    right = sort_list(mid)
    return merge(left, right)
 
def get_mid(head):
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    return mid

• sort_list is the recursion. If the list is empty or a single node it is already sorted, so we return it unchanged — that is the base case.
• mid = get_mid(head) finds the start of the second half and cuts the list, so head now refers only to the first half.
• left and right are the two halves sorted by the recursive calls; merge combines them. (A small merge helper walks both sorted lists, always splicing the smaller head onto the result.)
• In get_mid, fast starts one ahead and advances two nodes per loop. When fast falls off the end, slow is on the last node of the first half.
• slow.next = None severs the link between the halves so each half is its own independent list.

Complexity

Each level of recursion does O(n) total work merging, and there are O(log n) levels of splitting, giving O(n log n). The only extra space is the recursion stack, O(log n) — we never copy the values into an array, we just re-point existing nodes.

When this pattern shows up

Practice