Sorting a Linked List

July 2026 · 24 min read

Sorting is where the linked list flips the usual script. On an array, quicksort is king and merge sort pays an annoying tax; on a list, the tax vanishes and merge sort becomes not just the best choice but the obvious one. This post explains why, then builds four sorts — top-down merge, bottom-up merge, insertion, and quicksort by splicing — with correct, compilable C++ and the exact bugs that bite people writing them from memory.

Why std::sort Cannot Touch a List

Reach for the standard library first and you hit a wall:

std::list<int> lst = {5, 2, 8, 1};
std::sort(lst.begin(), lst.end());   // does not compile

std::sort is declared to take random-access iterators. Its introsort implementation computes mid = first + (last - first) / 2, jumps to a pivot, and partitions by walking two cursors toward each other from both ends — every one of those steps needs O(1) indexing. A std::list iterator is only bidirectional: it can do ++it and --it, but not it + n. The subtraction last - first is not even defined. The type system stops you before a single element moves.

That is why std::list carries its own sort as a member function:

lst.sort();               // uses operator<
lst.sort(std::greater<>{});  // custom comparator

And std::list::sort is a bottom-up merge sort internally — the exact algorithm we build below. It is required by the standard to be stable, and it never allocates a node: it only relinks the ones you already have.

Why Merge Sort Is The List Sort

Merge sort has two well-known irritations on arrays, and both come from the merge step:

• The O(n) merge buffer. Merging two sorted array runs in place is genuinely hard; the practical answer is to merge into a scratch array and copy back, costing O(n) extra memory.
• Merging is not in-place. You cannot interleave two sorted array segments without displacing elements, so you shuffle memory around.

Now watch what happens on a list. Merging two sorted lists is pure relinking — you compare the two front nodes, splice the smaller one onto the output tail, and advance. No element is copied; no buffer is allocated. The merge is O(1) extra space by construction:

// Merge two sorted lists by relinking. Nothing is copied.
ListNode* merge(ListNode* a, ListNode* b) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (a && 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 ? a : b;    // attach whatever remains
    return dummy.next;
}

So the two things that make merge sort awkward on an array — the buffer and the not-in-place merge — simply do not exist on a list. Meanwhile the things that make quicksort great on an array — cache locality and a tight in-place partition — disappear on a list: there is no locality to exploit, and partitioning a list means building new sublists, not swapping in place. The trade that favours quicksort on arrays reverses completely. On a linked list, merge sort keeps all of its advantages and loses all of its disadvantages.

Top-Down Merge Sort

The recursive formulation is the one everyone writes first: split the list in half with the fast/slow pointer trick, sort each half, merge. The whole algorithm is three moves.

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;    // 0 or 1 node is already sorted

    // --- split into two halves ---
    ListNode* slow = head;
    ListNode* fast = head->next;               // NOTE: fast starts one ahead
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* mid = slow->next;
    slow->next = nullptr;                       // cut the first half's tail

    ListNode* left  = sortList(head);
    ListNode* right = sortList(mid);
    return merge(left, right);
}

Two details decide whether this works or loops forever.

You must cut the first half. After the walk, slow sits on the last node of the first half. If you forget slow->next = nullptr, the "first half" still runs all the way to the end of the list, and merge will chase into the second half and produce garbage or a cycle. The cut is what turns one list into two.

Complexity. The recurrence is T(n) = 2·T(n/2) + O(n), giving O(n log n) time. Space is O(log n) for the recursion stack — not O(1), because each recursive frame is live while its two children run. That stack is the one thing bottom-up removes.

Bottom-Up Merge Sort — O(1) Extra Space

The bottom-up version throws away recursion entirely. Instead of splitting top-down, it builds sorted runs from the ground up: first treat every node as a sorted run of width 1, merge adjacent runs into runs of width 2, then width 4, 8, and so on until one run spans the whole list. No stack, no allocation — genuinely O(1) extra space. This is what std::list::sort and libstdc++'s list sort do.

It needs two helpers: split(head, n), which detaches the first n nodes and returns the rest, and a merge that appends onto a running tail so we can stitch pass after pass.

int listLength(ListNode* head) {
    int n = 0;
    for (ListNode* p = head; p; p = p->next) ++n;
    return n;
}

// Keep the first n nodes of `head` as a run; return the (n+1)-th node onward.
// If the list is shorter than n, return nullptr and leave `head` intact.
ListNode* split(ListNode* head, int n) {
    for (int i = 1; head && i < n; ++i) head = head->next;
    if (!head) return nullptr;
    ListNode* rest = head->next;
    head->next = nullptr;
    return rest;
}

// Merge a and b, appending onto *tailRef, and advance *tailRef to the new end.
void mergeInto(ListNode* a, ListNode* b, ListNode** tailRef) {
    ListNode* tail = *tailRef;
    while (a && 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 ? a : b;
    while (tail->next) tail = tail->next;    // walk to the real end
    *tailRef = tail;
}

ListNode* sortList(ListNode* head) {
    int n = listLength(head);
    ListNode dummy(0);
    dummy.next = head;

    for (int width = 1; width < n; width *= 2) {
        ListNode* cur  = dummy.next;
        ListNode* tail = &dummy;
        while (cur) {
            ListNode* left  = cur;
            ListNode* right = split(left,  width);   // left  = first  width nodes
            cur             = split(right, width);   // right = second width nodes
            mergeInto(left, right, &tail);           // merge them onto the output
        }
    }
    return dummy.next;
}

The outer loop runs log₂(n) times (each pass doubles width); each pass touches every node once, so it is O(n) per pass. Total: O(n log n) time, O(1) extra space, and it is stable because every merge uses <=. The dummy node means we never special-case an empty output tail.

Dry Run: bottom-up on 4→2→1→3

Four nodes, so n = 4 and the passes are width = 1 then width = 2 (the loop stops once width < n fails).

Notice the first pass merges [4] with [2] to get 2→4, and [1] with [3] to get 1→3; the second pass merges those two width-2 runs into the final answer. Two passes, four merges, zero allocations.

Insertion Sort on a List

Insertion sort is O(n²) in the worst case, but it has two real virtues on a list: it is O(1) extra space, and it is O(n) on already-sorted or nearly-sorted input — the case that shows up constantly in practice (log streams, append-mostly data). The list version also dodges the array version's biggest cost: there is no shifting. Inserting a node is a splice, not a memmove.

Keep a sorted prefix behind a dummy head, and for each incoming node either extend the run (fast path) or scan the prefix for its slot:

ListNode* insertionSortList(ListNode* head) {
    ListNode dummy(0);              // sorted region is dummy -> ... -> tail (null-terminated)
    ListNode* tail = &dummy;
    for (ListNode* cur = head; cur; ) {
        ListNode* next = cur->next;
        cur->next = nullptr;        // detach cur from the unsorted remainder
        if (tail != &dummy && tail->val <= cur->val) {
            tail->next = cur;       // fast path: input still ascending, append in O(1)
            tail = cur;
        } else {
            ListNode* p = &dummy;                       // scan the sorted prefix
            while (p->next && p->next->val <= cur->val)
                p = p->next;
            cur->next = p->next;    // splice cur in
            p->next = cur;
            if (p == tail) tail = cur;                  // ended up at the very end
        }
        cur = next;
    }
    return dummy.next;
}

The cur->next = nullptr right after saving next is the invariant that keeps the sorted region null-terminated at all times, so the scan loop can never run off into the still-unsorted tail. Drop that line and the fast-path append leaves cur->next pointing back into the unprocessed input — a classic corruption bug. On sorted input every node takes the fast path: O(n). On adversarial input every node scans the whole prefix: O(n²). Extra space is always O(1).

Quicksort by Splicing

You can quicksort a list. Pick a pivot, partition the nodes into three lists — less, equal, greater — recurse on the outer two, then concatenate. The three-way split handles duplicates cleanly.

ListNode* concat(ListNode* a, ListNode* b) {
    if (!a) return b;
    ListNode* t = a;
    while (t->next) t = t->next;
    t->next = b;
    return a;
}

ListNode* quickSortList(ListNode* head) {
    if (!head || !head->next) return head;
    int pivot = head->val;                 // first element as pivot (a weak choice)

    ListNode lessD(0), eqD(0), grtD(0);
    ListNode *lt = &lessD, *eq = &eqD, *gt = &grtD;
    for (ListNode* cur = head; cur; ) {
        ListNode* next = cur->next;
        cur->next = nullptr;
        if      (cur->val < pivot) lt = lt->next = cur;
        else if (cur->val == pivot) eq = eq->next = cur;
        else                        gt = gt->next = cur;
        cur = next;
    }

    ListNode* less = quickSortList(lessD.next);
    ListNode* grt  = quickSortList(grtD.next);
    return concat(less, concat(eqD.next, grt));   // less ++ equal ++ greater
}

It works, and yet nobody sorts production lists this way. Three reasons:

• Pivot choice is crippled. The trick that tames array quicksort — median-of-three, or a random index — needs O(1) access to arbitrary positions. On a list, "pick a random pivot" is an O(n) walk, and the cheap default (first element) is exactly the pivot that behaves worst.
• Worst case O(n²) on sorted input. With the first element as pivot, an already-sorted list puts everything into greater every time: n levels of recursion, O(n²) work, and O(n) stack — the precise input you most often receive.
• It surrenders quicksort's whole advantage. Array quicksort wins on cache locality and in-place partitioning. A list has neither: partitioning builds three brand-new chains, so you pay pointer-chasing costs with none of the locality payoff.

On stability: the array quicksort you know is not stable, because its in-place partition swaps equal keys past one another. This list version happens to preserve order within each bucket, so it can be made stable — but that buys nothing when merge sort is already stable, O(n log n) worst case, and O(1) space. Quicksort on a list is a curiosity, not a tool.

Stability — and Why It Matters

A sort is stable when equal keys keep their original relative order. Merge sort on a list is stable if and only if the merge breaks ties toward the left run:

if (a->val <= b->val) { take a; }   // <=  keeps equal elements in original order (STABLE)
// if you wrote < instead, ties go to b, and equal keys swap => UNSTABLE

The single character <= versus < is the entire difference between a stable and an unstable merge sort. Stability matters whenever the records carry more than the sort key. Sort a list of orders by price after it was already sorted by timestamp, and a stable sort leaves equal-priced orders in timestamp order — a free secondary sort. An unstable sort scrambles them. This is why std::stable_sort and std::list::sort exist as distinct, guaranteed-stable tools.

The Four Sorts, Side by Side

The takeaway is unusually clean for an algorithms topic: on a linked list, bottom-up merge sort is simply the answer. It is asymptotically optimal for a comparison sort, stable, and uses no extra memory. Every other option is either strictly worse or a special-case tool for nearly-sorted data.

Check Yourself

Each item gives a situation; pick the statement that is actually true.

Practice

• LeetCode 148 — Sort List merge sort write it top-down, then rewrite bottom-up for O(1) space.
• LeetCode 147 — Insertion Sort List insertion add the tail fast-path so sorted input is O(n).
• LeetCode 21 — Merge Two Sorted Lists merge the relinking primitive every list merge sort is built on.
• LeetCode 23 — Merge k Sorted Lists divide & conquer pairwise-merge the k lists like a merge-sort tree.
• LeetCode 912 — Sort an Array contrast implement merge sort on an array and feel the buffer you did not need on a list.