Sort a Linked List (Merge Sort)

Interview Prep

StandardLinked List Variation of Merge Two Sorted Listslinked-listsortingdivide-and-conquer

The problem

Sort a singly linked list in O(n log n) time. The challenge: most efficient array sorting algorithms (quicksort, heapsort) don't translate well to linked lists, because they assume constant-time random access.

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

Why merge sort is the natural fit

Merge sort needs only two primitives: split the list into halves, and merge two sorted lists. Both are cheap on linked lists — splitting at the middle is O(n) with the fast/slow pointer trick; merging is O(n) with the dummy-head technique from Merge Two Sorted Lists. Quicksort and heapsort want random access; merge sort doesn't.

Building blocks

def split_middle(head: Node) -> tuple[Node, Node]:
    """Find the middle with slow/fast pointers, then break the list into two halves."""
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None         # terminate the first half
    return head, mid

def merge(a: Node | None, b: Node | None) -> Node | None:
    dummy = Node()
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

Top-down (recursive) merge sort

def sort_list(head: Node | None) -> Node | None:
    """O(n log n) top-down merge sort.  O(log n) recursion stack."""
    if head is None or head.next is None:
        return head
    left, right = split_middle(head)
    return merge(sort_list(left), sort_list(right))

Trace

head: 4 -> 2 -> 1 -> 3

split_middle:
  slow starts at 4, fast at 2.
  fast=2, fast.next=1 -> slow=2, fast=3.
  fast=3, fast.next=None -> stop.
  mid = slow.next = 1.  slow.next = None.
  half1: 4 -> 2.  half2: 1 -> 3.

sort half1 = 4 -> 2:
  split: half1=[4], half2=[2].
  merge(4, 2) = 2 -> 4.

sort half2 = 1 -> 3:
  split: half1=[1], half2=[3].
  merge(1, 3) = 1 -> 3.

merge(2->4, 1->3) = 1 -> 2 -> 3 -> 4

Bottom-up: O(1) extra space

The recursive version is clear but uses O(log n) stack frames. The bottom-up variant sorts by repeatedly merging pairs of sublists of size 1, then 2, then 4, ..., walking the list in place each round. No recursion, no auxiliary heap memory beyond constant pointers. Worth knowing when an interviewer asks for "constant extra space".

def sort_list_iterative(head: Node | None) -> Node | None:
    """O(n log n) bottom-up merge sort.  O(1) extra space."""
    if head is None or head.next is None: return head

    # Count length
    n, p = 0, head
    while p: n, p = n + 1, p.next

    dummy = Node(0, head)
    size = 1
    while size < n:
        tail = dummy
        cur  = dummy.next
        while cur:
            left = cur
            right = split_off(left, size)         # cut after 'size' nodes
            cur   = split_off(right, size)        # cut next 'size' nodes; cur = remainder
            tail  = append_merged(tail, left, right)
        size *= 2
    return dummy.next

def split_off(head: Node | None, k: int) -> Node | None:
    """Walk k nodes forward, terminate, and return the (k+1)-th node (the next chunk's head)."""
    if head is None: return None
    for _ in range(k - 1):
        if head.next is None: break
        head = head.next
    rest, head.next = head.next, None
    return rest

def append_merged(tail, a, b):
    """Append merge(a, b) onto tail; return the new tail."""
    tail.next = merge(a, b)
    while tail.next: tail = tail.next
    return tail

Complexity

Time: O(n log n) for both versions.
Space: O(log n) recursive (call stack); O(1) bottom-up.

Why not quicksort?

Quicksort on linked lists works but has two drawbacks: choosing a good pivot is awkward without random access (you typically pick the head, which is worst-case O(n²) on already-sorted input), and partitioning is harder to make in place. Merge sort sidesteps both — equal split is just "advance slow once for every two steps of fast", and merging is symmetric and stable.

Stability matters in many real applications (you often want to sort by one key while preserving the relative order from another). Merge sort is stable; the standard linked-list quicksort isn't.