Sort List Bottom-Up — O(1) Space Merge Sort on Linked Lists

Problem Statement#

LeetCode 148 — Sort List (Bottom-Up Merge Sort) Difficulty: Hard | Pattern: Bottom-Up Iterative Merge Sort

Given the head of a linked list, return the list sorted in ascending order. The follow-up challenge — and the hard part — is to sort in O(n log n) time and O(1) space (i.e., without recursive stack space).

Constraints:

• Number of nodes: 0 <= n <= 5 * 10^4
• -10^5 <= Node.val <= 10^5

Example 1:

Input:  head = [4, 2, 1, 3]
Output: [1, 2, 3, 4]

Example 2:

Input:  head = [-1, 5, 3, 4, 0]
Output: [-1, 0, 3, 4, 5]

Why This Problem Matters#

Sorting a linked list is asked at Amazon, Google, and Facebook because it tests whether you understand why familiar sorting algorithms work differently on linked lists compared to arrays:

• Quick sort: O(1) space on arrays. On linked lists, the random pivot access does not help — still O(n log n) average but O(n²) worst case without careful pivot selection.
• Top-down merge sort: O(n log n) but uses O(log n) recursive stack space.
• Bottom-up merge sort: O(n log n) and O(1) space — the optimal solution.

The bottom-up approach mirrors how external merge sort works — a critical algorithm in database systems and distributed data processing. Instead of recursing to the smallest subproblems (size 1) and returning, you start from size 1 and repeatedly double the merge width until the whole list is sorted.

What makes implementation tricky on a linked list (compared to arrays) is that splitting requires traversal (no random access), and reconnecting merged segments must be done with precise pointer bookkeeping. This is the test: can you implement a non-trivial algorithm correctly without the safety net of array indexing?

The Core Insight#

Top-down merge sort (simpler): Split the list recursively using fast/slow pointers, sort each half, merge. Uses O(log n) stack space.

Bottom-up merge sort (optimal): Process the list in passes with doubling step sizes.

• Pass 1: merge pairs of sublists of size 1. (Sorted pairs)
• Pass 2: merge pairs of sublists of size 2. (Sorted groups of 4)
• Pass 3: merge pairs of sublists of size 4. (Sorted groups of 8)
• Continue until step size >= n.

Each pass touches all n nodes once: O(n) per pass, O(log n) passes total = O(n log n).

For each merge in a pass, you need two helpers:

• split(head, size): Walk size steps and cut the list, returning the head of the second half.
• merge(l1, l2): Standard merge of two sorted lists, returning (merged_head, merged_tail).

The tail pointer from merge is critical: after merging two sublists, you need to attach the next sublist pair to the tail of the merged result.

Visual Dry Run#

Input: [4, 2, 1, 3]

Pass 1 (size=1): merge pairs of size 1:

Split [4] and [2]: merge -> [2, 4]  (tail=4)
Split [1] and [3]: merge -> [1, 3]  (tail=3)
Reconnect: dummy -> [2, 4] -> [1, 3]

Pass 2 (size=2): merge pairs of size 2:

Split [2, 4] and [1, 3]: merge -> [1, 2, 3, 4]  (tail=4)
No more pairs.

Result: [1, 2, 3, 4]

Solution (Optimal — Bottom-Up)#

from typing import Optional
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def sortList(head: Optional[ListNode]) -> Optional[ListNode]:
    # Count length
    n = 0
    curr = head
    while curr:
        n += 1
        curr = curr.next
 
    dummy = ListNode(0)
    dummy.next = head
 
    size = 1
    while size < n:
        curr = dummy.next
        tail = dummy  # tail of the last merged segment
 
        while curr:
            # Split two sublists of length 'size'
            left = curr
            right = split(left, size)
            curr = split(right, size)
 
            # Merge the two sublists
            merged_head, merged_tail = merge(left, right)
            tail.next = merged_head
            tail = merged_tail
 
        size <<= 1  # double the sublist size
 
    return dummy.next
 
 
def split(head: Optional[ListNode], size: int) -> Optional[ListNode]:
    """Walk 'size' steps and cut the list. Returns head of the remainder."""
    for _ in range(size - 1):
        if head and head.next:
            head = head.next
        else:
            break
    if not head:
        return None
    rest = head.next
    head.next = None
    return rest
 
 
def merge(l1: Optional[ListNode], l2: Optional[ListNode]):
    """Merge two sorted lists. Returns (head, tail) of merged list."""
    dummy = ListNode(0)
    curr = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2
    # Advance curr to actual tail
    while curr.next:
        curr = curr.next
    return dummy.next, curr

function sortList(head) {
    if (!head || !head.next) return head;
 
    // Count length
    let n = 0;
    let curr = head;
    while (curr) { n++; curr = curr.next; }
 
    const dummy = { val: 0, next: head };
 
    for (let size = 1; size < n; size <<= 1) {
        curr = dummy.next;
        let tail = dummy;
 
        while (curr) {
            const left = curr;
            const right = split(left, size);
            curr = split(right, size);
 
            const [mergedHead, mergedTail] = mergeSorted(left, right);
            tail.next = mergedHead;
            tail = mergedTail;
        }
    }
 
    return dummy.next;
}
 
function split(head, size) {
    for (let i = 0; i < size - 1 && head && head.next; i++) {
        head = head.next;
    }
    if (!head) return null;
    const rest = head.next;
    head.next = null;
    return rest;
}
 
function mergeSorted(l1, l2) {
    const dummy = { val: 0, next: null };
    let curr = dummy;
    while (l1 && l2) {
        if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
        else { curr.next = l2; l2 = l2.next; }
        curr = curr.next;
    }
    curr.next = l1 || l2;
    while (curr.next) curr = curr.next;
    return [dummy.next, curr];
}

Complexity:

Common Mistakes#

1. Using top-down merge sort (recursive): Valid for O(n log n) time, but uses O(log n) stack space. The "hard" version of this problem requires O(1) space — the bottom-up approach.
2. Wrong split logic: split(head, size) should walk size - 1 additional steps (not size), then cut. Walking size steps leaves the cut one node too late.
3. Not tracking the tail of merged segments: The tail pointer is essential for connecting merged segments correctly in each pass. Without it, you lose the connection between merged groups.
4. Not advancing curr after split(right, size): After splitting off the right sublist, curr must jump to the next unprocessed pair. The second split call does this.
5. Forgetting to double size: The outer while loop condition is size < n and size <<= 1 at the end of each pass. Missing the doubling creates an infinite loop.

Interview Tips#

• Start with top-down: "The straightforward approach is top-down merge sort — O(n log n) time and O(log n) stack space. If you need O(1) space, I'll use bottom-up."
• Explain the doubling strategy: "I merge pairs of sublists of size 1, then 2, then 4 — doubling each pass. After log n passes, the list is fully sorted."
• Draw a pass: Trace [4,2,1,3] through Pass 1 (size=1) and Pass 2 (size=2) on the whiteboard.
• Explain why tail tracking matters: "After merging each pair, I attach the result to the previous merged segment using the tail pointer. Without it, I cannot reconnect the chain."
• Mention the split helper: "The split function walks size steps and cuts the list, returning the head of the right half. It is the key building block."

Follow-up Questions#

1. Top-down merge sort on linked list: Show the recursive approach first. When interviewer asks for O(1) space, transition to bottom-up.
2. Why not use quicksort? On linked lists, quicksort is still O(n log n) average but O(n²) worst case and does not offer the O(n log n) guarantee.
3. Can you sort in O(n)? Only for special inputs — e.g., counting sort for small value ranges. General comparison-based sorting requires O(n log n).
4. What is external merge sort? The same bottom-up doubling strategy applied to data on disk — merge k sorted files at a time using a heap.
5. LeetCode 23 — Merge K Sorted Lists: The merge helper here is the same as the base operation in merge K sorted lists.

Key Takeaways#

• Bottom-up merge sort achieves O(n log n) time and O(1) space by iteratively doubling the merge width, eliminating the O(log n) recursive call stack.
• Three key helpers: split(head, size) cuts the list, merge(l1, l2) merges two sorted sublists and returns both head and tail.
• The tail pointer connects consecutive merged segments within each pass — without it, the merged groups would be disconnected.
• The outer loop runs O(log n) times (doubling size each pass); each pass processes all n nodes: O(n log n) total.
• This is the same principle behind external merge sort — a critical algorithm in databases and distributed data processing.
• Mastering this problem demonstrates the ability to implement a non-trivial algorithm without recursion, which is a strong signal in senior-level interviews.