Sort List | Merge Sort O(n log n) O(1) Space | Linked List

Overview

Sort list means sorting a linked list in ascending order. The standard approach is merge sort: O(n log n) time and O(log n) space for the recursion stack (or O(1) if you use an iterative bottom-up merge). Steps: (1) Split the list in half using Find Middle (fast/slow pointers), (2) Recursively sort the two halves, (3) Merge the sorted halves with Merge Two Sorted. Base case: list of length 0 or 1 is already sorted.

Key idea: Linked lists don't allow O(1) random access, so merge sort (split in the middle, recurse, merge) is a natural fit. Quicksort is possible with partition but typically needs more care; merge sort is stable and consistently O(n log n).

When to Use

Sort a linked list — Exact problem; O(n log n) required or desired.
Stable sort — Merge sort is stable (equal elements keep relative order).

How It Works

Base case: If head is null or head.next is null, return head.
Find middle: Use fast/slow; when fast reaches the end, slow is at the last node of the first half. Set mid = slow.next, then slow.next = null to split.
Recurse: left = sortList(head), right = sortList(mid).
Merge: return mergeTwoLists(left, right).

Example 1: Sort List (Merge Sort)

Problem: Given the head of a linked list, sort it in O(n log n) time and O(log n) space.

function sortList(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return head;
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  let prev: ListNode | null = null;
  while (fast !== null && fast.next !== null) {
    prev = slow;
    slow = slow!.next;
    fast = fast.next.next;
  }
  prev!.next = null;
  const left = sortList(head);
  const right = sortList(slow);
  return mergeTwoLists(left, right);
}
function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummy = new ListNode(-1);
  let tail = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
    else { tail.next = l2; l2 = l2.next; }
    tail = tail.next;
  }
  tail.next = l1 ?? l2;
  return dummy.next;
}

Time: O(n log n), Space: O(log n) recursion.

Example 2: Iterative (Bottom-Up) Merge Sort

Idea: Merge sublists of size 1, then 2, then 4, etc., until the whole list is merged. No recursion; O(1) extra space (excluding the list itself). Implementation is longer: maintain a sublist size, sweep through the list splitting and merging segments of that size, then double the size.

Edge Cases

Empty list — Return null.
Single node — Base case; return head.
Two nodes — Split into two single-node lists, merge; correct.

Common Mistakes

Not splitting — Set prev.next = null (or slow.next = null) so the list is actually cut; otherwise recursion never terminates.
Wrong middle — For merge sort you want the first half to end at slow (so first half has the middle node or the first of two middles); set mid = slow.next and cut before mid so the halves are roughly equal.
Losing merge result — Return the result of mergeTwoLists, not head or mid.

Time and Space Complexity

Time: O(n log n).
Space: O(log n) for recursion; O(1) for iterative bottom-up.

Summary

Sort list: Find middle → split → sortList(left), sortList(right) → merge(left, right).
Uses Find Middle and Merge Two Sorted. See Fast and Slow Pointers for the split.

Sort List (Merge Sort on List)