Merge Sort For Linked lists

The problem, simply

You get the head of a linked list of numbers. Sort it from small to big and return the new head. Do it by changing arrows, not by copying the numbers somewhere else.

Merge sort is the sort of choice for linked lists. It never needs to jump to the middle of the list by position, it only walks forward, and merging two sorted lists needs no extra boxes.

A story to remember it

Picture it

Examples

Way 1: the simple way

Copy the numbers into an array, sort the array, and write them back.

1. Walk the list and put every number in an array.
2. Sort the array with the built in sort.
3. Walk the list again and write the sorted numbers back into the boxes, in order.

class Solution {
    public ListNode sortList(ListNode head) {
        List<Integer> vals = new ArrayList<>();
        for (ListNode p = head; p != null; p = p.next) vals.add(p.val);
        Collections.sort(vals);
        int i = 0;
        for (ListNode p = head; p != null; p = p.next) p.val = vals.get(i++);  // write back
        return head;
    }
}

How long it takes: sorting the copy is O(n log n). Extra room: the copy, O(n). Interviewers usually reject this because it does not sort the list itself, and in real code the boxes may carry more than a number.

Way 2: the clever way

Merge sort, made for lists.

1. If the list has zero or one box, it is sorted. Return it.
2. Find the middle with slow and fast pointers. Start fast one box ahead so that slow stops at the end of the left half.
3. Cut: save slow.next as the head of the right half, then set slow.next = null.
4. Sort the left half and the right half with the same method.
5. Merge the two sorted halves with two fingers and a dummy box, always taking the smaller front box.

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;   // one box is sorted
        ListNode slow = head, fast = head.next;                // fast one ahead: slow ends the left half
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode right = slow.next;
        slow.next = null;                                      // cut the list in two
        return merge(sortList(head), sortList(right));
    }

    private ListNode merge(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0), tail = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }   // <= keeps it stable
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = (a != null) ? a : b;                      // glue on the rest
        return dummy.next;
    }
}

How long it takes: the list is cut in half about log n times, and each level of cutting and merging walks all n boxes, so O(n log n). Extra room: no new boxes, but the waiting calls stack up log n deep, O(log n).

Another way: bottom up, no recursion

LeetCode 148 asks for O(1) extra room. Skip the recursion and build up instead. First merge pieces of size 1 in pairs, so every run of 2 is sorted. Then merge runs of 2 into runs of 4, then 8, until one run covers the list.

class Solution {
    public ListNode sortList(ListNode head) {
        int n = 0;
        for (ListNode p = head; p != null; p = p.next) n++;
        ListNode dummy = new ListNode(0, head);
        for (int size = 1; size < n; size *= 2) {             // runs of 1, 2, 4, ...
            ListNode prev = dummy, curr = dummy.next;
            while (curr != null) {
                ListNode left = curr;
                ListNode right = split(left, size);           // cut off a run of size
                curr = split(right, size);                    // and the next run
                prev = merge(left, right, prev);              // hang the merged run after prev
            }
        }
        return dummy.next;
    }

    // Cut after size boxes and return the head of what is left.
    private ListNode split(ListNode head, int size) {
        for (int i = 1; head != null && i < size; i++) head = head.next;
        if (head == null) return null;
        ListNode rest = head.next;
        head.next = null;
        return rest;
    }

    // Merge a and b after prev, and return the last box of the merged run.
    private ListNode merge(ListNode a, ListNode b, ListNode prev) {
        ListNode tail = prev;
        while (a != null && b != null) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = (a != null) ? a : b;
        while (tail.next != null) tail = tail.next;
        return tail;
    }
}

Same O(n log n) time, and only a handful of fingers, O(1) extra room.

Watch out for

• Forgetting slow.next = null. Without the cut, the left half still runs into the right half, and the recursion never ends.
• Using < in the merge. It still sorts, but equal numbers can swap order, so the sort is no longer stable.
• Forgetting to glue the rest of the longer half after the merge loop.
• Thinking merge sort on a list needs O(n) extra room like on an array. On a list the merge only rewires arrows.

What interviewers ask next

• Why merge sort and not quicksort for lists? Quicksort wants to jump to any position and swap, which is slow on a list. Merge sort only walks forward and merges by rewiring, so it fits lists perfectly.
• Can you do it in O(1) extra room? Yes, the bottom up version above.
• Is it stable? Yes, if the merge takes from the left half on ties (<=).
• Sort a doubly linked list. Same steps, and fix the prev arrows during the merge.
• Merge k sorted lists, or count inversions. Both reuse this merge step.

Remember this

Grown-up words: splitting the pile is divide and conquer, the helpers are recursive calls, zipping two sorted piles is the merge step, the dummy box is a sentinel node, keeping ties in order is stability, and the size 1, 2, 4 version is bottom up merge sort.