DSA Sorting a Linked List

The problem

Sorting a linked list takes a chain of nodes and returns the same nodes in rising value order. A node holds one value and a next link to the following node. The chain has no index access, so no step may jump straight to a position.

The answer is the head of the sorted chain. An empty chain sorts to an empty chain. The cases below are the ones this article uses throughout.

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

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def values_of(head):
    out = []
    while head is not None:
        out.append(head.value)
        head = head.next
    return out

cases = [
    ([4, 2, 1, 3], [1, 2, 3, 4]),
    ([7, 2, 9, 4, 1, 8, 3, 5], [1, 2, 3, 4, 5, 7, 8, 9]),
    ([5, 4, 3, 2, 1], [1, 2, 3, 4, 5]),
    ([1], [1]),
    ([], []),
]
for values, expected in cases:
    print("values", values, "-> sorted:", expected)

Read one row at a time. The second row is the long one, with eight values in no clear order. The last two rows are the short chains, where sorting has almost nothing to do.

Intuition: take the smallest value again and again

The first idea looks for the smallest value, takes it, and repeats. Each pass scans every value that is still left. The smallest value comes out first, then the next smallest, and so on.

The idea always works. Its cost is the trap. Every pass rescans the shrinking remainder, and the scans add up to nearly the square of the length.

values = [5, 4, 3, 2, 1]
work = list(values)
result = []
comparisons = 0
while work:
    smallest = 0
    for i in range(1, len(work)):
        comparisons += 1
        if work[i] < work[smallest]:
            smallest = i
    result.append(work.pop(smallest))
print("sorted:", result)
print("comparisons:", comparisons)

Five values cost ten comparisons here. The first scan alone costs four, and the scans only shrink by one each pass. A chain twice as long costs roughly four times as much.

Brute force: copy the values out and selection sort them

The brute force walks the chain once and copies its values into a Python list. It then runs the take-the-smallest scan on that list. A fresh chain is built from the sorted values at the end.

A counter records every comparison the scans make. The no-pair style bad case for this sort is a reversed chain, because every scan runs to the very end of the remainder.

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

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def values_of(head):
    out = []
    while head is not None:
        out.append(head.value)
        head = head.next
    return out

def brute_sort(head):
    values = values_of(head)
    comparisons = 0
    out = []
    work = list(values)
    while work:
        smallest = 0
        for i in range(1, len(work)):
            comparisons += 1
            if work[i] < work[smallest]:
                smallest = i
        out.append(work.pop(smallest))
    return build(out), comparisons

for values in ([4, 2, 1, 3], [5, 4, 3, 2, 1]):
    sorted_head, comparisons = brute_sort(build(values))
    print("values", values, "->", values_of(sorted_head), "comparisons:", comparisons)

The reversed five values cost the full ten comparisons. Nothing in the method ever skips a scan. The optimal solution below keeps the work on the chain itself and splits the problem instead of rescanning it.

The optimal solution: split in half, sort each half, merge

Merge sort splits the chain at its middle, sorts each half, and merges the two sorted halves by taking the smaller front node each time. That one sentence is the whole method.

This method is divide and conquer. One problem is split into smaller copies of itself. Each copy is solved on its own. The answers are then combined into one answer.

A slow pointer and a fast pointer find the middle. The slow pointer moves one link per step and the fast pointer moves two, so the slow pointer stops at the split point. Cutting one link there leaves two shorter chains.

The merge uses a dummy head, a throwaway node placed before the result. Every winner is linked behind the tail, with no special case for the first node. The sort relinks the existing nodes, and no new value nodes are created.

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

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def values_of(head):
    out = []
    while head is not None:
        out.append(head.value)
        head = head.next
    return out

def merge(first, second):
    dummy = Node(0)
    tail = dummy
    one, two = first, second
    while one is not None and two is not None:
        if one.value <= two.value:
            tail.next = one
            one = one.next
        else:
            tail.next = two
            two = two.next
        tail = tail.next
    tail.next = one if one is not None else two
    return dummy.next

def sort_list(head):
    if head is None or head.next is None:
        return head
    slow = head
    fast = head.next
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    second = slow.next
    slow.next = None
    return merge(sort_list(head), sort_list(second))

cases = [
    ([4, 2, 1, 3], [1, 2, 3, 4]),
    ([7, 2, 9, 4, 1, 8, 3, 5], [1, 2, 3, 4, 5, 7, 8, 9]),
    ([5, 4, 3, 2, 1], [1, 2, 3, 4, 5]),
    ([1], [1]),
    ([], []),
]
for values, expected in cases:
    result = values_of(sort_list(build(values)))
    print("values", values, "->", result, "expected:", expected, "match:", result == expected)

All five cases pass. Splitting and merging both follow next links. Neither move needs an index, which is why merge sort fits a chain so well.

Walkthrough: sorting [4, 2, 1, 3]

The walk follows one sort from the first split to the last merge. Each line prints one split or one merge. The merges rebuild the answer from the smallest pieces upward.

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

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def values_of(head):
    out = []
    while head is not None:
        out.append(head.value)
        head = head.next
    return out

def merge(first, second):
    dummy = Node(0)
    tail = dummy
    one, two = first, second
    while one is not None and two is not None:
        if one.value <= two.value:
            tail.next = one
            one = one.next
        else:
            tail.next = two
            two = two.next
        tail = tail.next
    tail.next = one if one is not None else two
    merged = dummy.next
    print("merge ->", values_of(merged))
    return merged

def sort_list(head):
    if head is None or head.next is None:
        return head
    slow = head
    fast = head.next
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    second = slow.next
    slow.next = None
    print("split", values_of(head), "and", values_of(second))
    return merge(sort_list(head), sort_list(second))

print("sorted:", values_of(sort_list(build([4, 2, 1, 3]))))

The first split makes two chains of two. Each of those splits into single nodes, and single nodes are already sorted. The merges then join 4 with 2, 1 with 3, and finally the two sorted halves.

Complexity

Each level of splitting passes every node through one merge, and the number of levels is the number of halvings of n, so the time is O(n log n). The brute force scan costs n times n minus 1, divided by 2, comparisons, so its time is O(n^2).

The recursion depth grows with the halvings of the length, not with the length itself, so the extra space is O(log n). The brute force also builds a full copy of the values, which costs O(n) extra space.

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

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def values_of(head):
    out = []
    while head is not None:
        out.append(head.value)
        head = head.next
    return out

count = [0]

def merge(first, second):
    dummy = Node(0)
    tail = dummy
    one, two = first, second
    while one is not None and two is not None:
        count[0] += 1
        if one.value <= two.value:
            tail.next = one
            one = one.next
        else:
            tail.next = two
            two = two.next
        tail = tail.next
    tail.next = one if one is not None else two
    return dummy.next

def sort_list(head):
    if head is None or head.next is None:
        return head
    slow = head
    fast = head.next
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    second = slow.next
    slow.next = None
    return merge(sort_list(head), sort_list(second))

for n in (8, 16, 32):
    count[0] = 0
    sort_list(build(list(range(n, 0, -1))))
    brute = n * (n - 1) // 2
    print("values", n, "- brute comparisons:", brute, " merge comparisons:", count[0])

Counts beat clocks here. At 32 values the scan count is 496 against 80 merge comparisons. The gap widens with every doubling.

Edge cases and pitfalls

The classic mistake is splitting without cutting the link. If the first half still points into the second half, the two halves are not separate chains and the recursion never shrinks. The line that sets the split node's next to None is part of the algorithm.

A second mistake is losing the second half before the cut. The split must save the head of the second half first, and only then cut the link.

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

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def values_of(head):
    out = []
    while head is not None:
        out.append(head.value)
        head = head.next
    return out

def merge(first, second):
    dummy = Node(0)
    tail = dummy
    one, two = first, second
    while one is not None and two is not None:
        if one.value <= two.value:
            tail.next = one
            one = one.next
        else:
            tail.next = two
            two = two.next
        tail = tail.next
    tail.next = one if one is not None else two
    return dummy.next

def sort_list(head):
    if head is None or head.next is None:
        return head
    slow = head
    fast = head.next
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    second = slow.next
    slow.next = None
    return merge(sort_list(head), sort_list(second))

print("empty:", values_of(sort_list(build([]))))
print("one node:", values_of(sort_list(build([1]))))
print("already sorted:", values_of(sort_list(build([1, 2, 3]))))
print("duplicates:", values_of(sort_list(build([2, 2, 1, 1]))))
print("negatives:", values_of(sort_list(build([-3, 5, -1, 0]))))

Duplicates stay in the result, one node per copy. The merge takes from the first chain on a tie, so equal values keep their input order.