Quicksort for Linked Lists

The problem, simply

You get a linked list of numbers: a chain of boxes, each pointing to the next. Sort it from small to big using quicksort, and give back the new first box.

Quicksort works like this: choose one number as the judge (the pivot). Put everything smaller than the judge on its left and everything bigger on its right. Now the judge is in its final spot, and you sort the left part and the right part the same way.

On an array this is easy because you can jump to any spot. On a chain you can only walk forward, so you have to be smart about how you split.

A story to remember it

Picture it

Examples

Way 1: the simple way

Leave the boxes where they are and move the numbers. This is array quicksort, done with two fingers that only walk forward.

1. The judge is the number in the first box, start.
2. Finger i marks the end of the "smaller than the judge" part. It starts on start.
3. Finger j walks from the second box to the end. When j finds a smaller number, move i one box forward and swap the numbers in i and j.
4. At the end, swap the judge's number into box i. Now the judge sits in its final spot.
5. Sort the boxes before i and the boxes after i the same way.

class Solution {
    public ListNode quickSort(ListNode head) {
        sort(head, null);      // sort from head up to (not including) null
        return head;
    }

    // sort the boxes from start up to, but not including, end
    private void sort(ListNode start, ListNode end) {
        if (start == end || start.next == end) return;   // 0 or 1 box
        ListNode i = start;                               // end of the smaller part
        for (ListNode j = start.next; j != end; j = j.next) {
            if (j.val < start.val) {
                i = i.next;
                swap(i, j);                               // move the small number left
            }
        }
        swap(start, i);                                   // the judge goes to its spot
        sort(start, i);                                   // left part
        sort(i.next, end);                                // right part
    }

    private void swap(ListNode a, ListNode b) {
        int t = a.val; a.val = b.val; b.val = t;
    }
}

How long it takes: each round walks its part once. If the judge splits parts nicely in half, there are about log n rounds of splitting, so O(n log n). If the judge is always the smallest (a sorted chain) or every number is the same, each round removes one box and it becomes O(n^2). Extra room: the waiting helpers of the recursion, O(log n) on average and O(n) in the worst case. Moving numbers is not allowed in some interviews, because a real box may carry much more than one number.

Way 2: the clever way

Move the boxes, not the numbers. This is what the teacher did with the three lines.

1. The judge is the number in the first box.
2. Walk the chain once. Unhook each box and hook it to the end of one of three little chains: smaller, same, or bigger.
3. Cut the end of each little chain so it points to null.
4. Sort the smaller chain and the bigger chain with the same steps. The same chain is already sorted, since all its numbers are equal.
5. Glue them: smaller, then same, then bigger.

class Solution {
    public ListNode quickSort(ListNode head) {
        if (head == null || head.next == null) return head;   // 0 or 1 box
        int judge = head.val;
        ListNode lessDummy = new ListNode(0), sameDummy = new ListNode(0), moreDummy = new ListNode(0);
        ListNode less = lessDummy, same = sameDummy, more = moreDummy;   // tails of the three lines
        for (ListNode cur = head; cur != null; cur = cur.next) {
            if (cur.val < judge) { less.next = cur; less = cur; }
            else if (cur.val > judge) { more.next = cur; more = cur; }
            else { same.next = cur; same = cur; }
        }
        less.next = null; same.next = null; more.next = null;   // cut the old arrows

        ListNode sortedLess = quickSort(lessDummy.next);
        ListNode sortedMore = quickSort(moreDummy.next);

        same.next = sortedMore;                       // same line, then bigger line
        if (sortedLess == null) return sameDummy.next;
        ListNode tail = sortedLess;
        while (tail.next != null) tail = tail.next;   // find the end of the smaller line
        tail.next = sameDummy.next;                   // smaller line, then same line
        return sortedLess;
    }
}

How long it takes: each round walks its boxes once, so O(n log n) on average and O(n^2) when the judge is always the smallest or biggest (a sorted chain). A chain where every number is the same is now fast, O(n), because all the equal boxes go into the same line at once. Extra room: only the waiting helpers of the recursion, O(log n) on average and O(n) in the worst case. No new boxes are made apart from three tiny dummy boxes per round.

A bonus: boxes are always hooked to the end of their line, so equal numbers keep their old order. This version is stable, which array quicksort is not.

Watch out for

• The sorted chain is the slow case when the judge is the first box. Pick a random box as the judge instead. Walking to it costs O(n), which a round already spends anyway.
• In Way 1, the right part starts at i.next, not i. Including the judge again recurses forever when nothing is smaller than the judge.
• Return the new head. In Way 2 the first box of the answer is usually not the old head.
• A two way split (smaller, not smaller) that keeps the judge inside never shrinks a chain of equal numbers, so the recursion never ends. The three way split avoids that.

What interviewers ask next

• Which sort is better for linked lists? Merge sort. It always takes O(n log n), it is stable, and merging two chains needs no extra room. Quicksort's strength on arrays is fast jumping and cache friendliness, which chains do not have.
• How do you avoid the O(n^2) case? Pick the judge at random, or use the middle box (found with slow and fast fingers). Neither removes the worst case completely, but it becomes very unlikely.
• Can you avoid walking to the end of the smaller line? Yes. Let the helper return both the head and the tail of its sorted chain, as a pair.
• Can you sort a linked list with O(1) extra room? Bottom up merge sort: merge runs of size 1, then 2, then 4, with a loop instead of recursion.

Remember this

Grown-up words: the judge is the pivot, the three lines are a three way partition, the fake front boxes are dummy nodes, keeping equal items in order is stability, and the waiting helpers are the recursion stack.