Merge Sort Example: Sorting a Linked List

A linked list cannot be indexed, but it can be split and merged by relinking nodes.

Merge sort is the usual way to sort a singly linked list, because every step it takes walks the list from the front and none of them needs to jump to an index. This example sorts a six-node list, finding the middle by counting and merging by relinking nodes instead of copying them into a buffer.

A singly linked list is a chain of nodes, each holding a value and a next reference to the node after it. Reaching the k-th node means following k links from the head, so a sort that jumps around by index, as quicksort's partition and heapsort do on an array, pays O(n) for every jump. Merge sort only ever moves forward: count to the middle, cut, sort each half, and merge by looking at the two front nodes. The steps below come from a run that sorted 9 → 4 → 7 → 2 → 8 → 1 and printed the list at each stage of the top-level split and merge.

Sorting a six-node linked list, at the top level of the recursion

Count to the middle and cut

Walk the list once to count its six nodes, then walk again to the third node, the last of the first half, and set its next to nothing. That one change splits the list into two lists of three, with no node copied.

text

list: 9 -> 4 -> 7 -> 2 -> 8 -> 1
cut: 9 -> 4 -> 7 | 2 -> 8 -> 1

Sort each half the same way

Each half is a shorter linked list, so the same function sorts it, cutting and merging until the pieces have one node. Both come back sorted.

text

sorted halves: 4 -> 7 -> 9 | 1 -> 2 -> 8

Take 1 and 2 from the right

The merge keeps a tail, the last node of the merged list. It compares the two front nodes, links the smaller one after tail, and moves that list's front on. 1 beats 4, then 2 beats 4, so both come from the right half.

text

merged: 1 -> 2
  left: 4 -> 7 -> 9
  right: 8

Take 4 and 7 from the left

8 is now the right half's front, and 4 and 7 are both smaller, so the left half gives twice. Each take changes one next reference; the nodes themselves never move.

text

merged: 1 -> 2 -> 4 -> 7
  left: 9
  right: 8

Take 8 from the right

8 beats 9, and the right half is empty, so the comparing is over.

text

merged: 1 -> 2 -> 4 -> 7 -> 8
  left: 9
  right: (empty)

Link the rest

Whatever remains of the other half is already sorted and already linked together, so one assignment attaches all of it: tail.next becomes the node holding 9. On an array this is a loop that copies the rest; on a list it is a single link however many nodes remain.

text

merged: 1 -> 2 -> 4 -> 7 -> 8 -> 9
  left: (empty)
  right: (empty)

The run finished with 1 → 2 → 4 → 7 → 8 → 9. Two things differ from the array version. Finding the middle costs O(n) instead of O(1), because the list has to be walked, but each level already spends O(n) merging, so the total stays O(n log n). And the merge needs no buffer: it relinks the nodes it already has, so the only extra memory is the O(log n) stack of recursive calls. Merge sort on a linked list is still stable, as long as a tie takes the left node.

The pattern carries over to anything that can only be read from the front: a linked list, a stream, or sorted files on disk read one record at a time. Where an array lets you jump, merge sort never needs to, which is why Java's LinkedList is sorted by copying it to an array first, while a hand-built list is usually sorted by relinking its own nodes, as here.

← → move through sections and cards