Why Quicksort is preferred for Arrays and Merge Sort for LinkedLists

The problem, simply

This is a "why" question. Both quicksort and merge sort take about n log n steps on average. Yet on arrays people pick quicksort, and on linked lists people pick merge sort. Explain why, and be ready to write both.

The short answer: each sort needs a different thing from the data. Quicksort needs to jump and swap cheaply. Merge sort needs to glue pieces together cheaply. Arrays are great at the first, chains are great at the second.

A story to remember it

Picture it

Examples

Way 1: the simple way

Quicksort, the array champion. Pick a judge (the pivot), move smaller numbers to its left and bigger ones to its right by swapping, then sort both sides.

1. Pick a random slot as the judge, which costs one jump in an array.
2. Walk j over the part. Each time a[j] is smaller than the judge, swap it to the front zone with finger i.
3. Put the judge right after the front zone. Sort the left side and the right side.

Why it fits arrays: every swap is two jumps, the walk reads neighbor slots that the computer already loaded together (cache friendly), and no second array is needed.

Why it does not fit lists: a random judge costs a walk of O(n); the fast two-ended partition needs to walk backwards; boxes are scattered in memory, so the cache bonus is gone; and swapping numbers instead of boxes is often not allowed.

import java.util.*;

class Solution {
    private final Random rnd = new Random();

    public void quickSort(int[] a) { sort(a, 0, a.length - 1); }

    private void sort(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        swap(a, lo + rnd.nextInt(hi - lo + 1), hi);   // random judge, jump in O(1)
        int judge = a[hi], i = lo;
        for (int j = lo; j < hi; j++) {
            if (a[j] < judge) swap(a, i++, j);        // grow the smaller zone
        }
        swap(a, i, hi);                               // judge goes to its final slot
        sort(a, lo, i - 1);
        sort(a, i + 1, hi);
    }

    private void swap(int[] a, int x, int y) { int t = a[x]; a[x] = a[y]; a[y] = t; }
}

How long it takes: O(n log n) on average, O(n^2) in the unlucky worst case (rare with a random judge). Extra room: only the recursion, O(log n) on average.

Way 2: the clever way

Merge sort, the list champion. Cut the chain in the middle, sort each half, then zip the two sorted halves together.

1. Find the middle with two runners: slow moves 1 box, fast moves 2.
2. Cut after slow. Now there are two chains.
3. Sort each chain the same way, until chains have one box.
4. Merge: look at the front box of both chains, hook the smaller one to the answer, move on.

Why it fits lists: the cut is one arrow change, and the merge only rewires arrows, so no second array is needed. It always splits in half, so it is always O(n log n), and taking from the left chain on ties keeps equal items in order.

Why it is weaker on arrays: merging two halves of an array needs a helper array of size n, which costs memory and copying.

class Solution {
    public ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {   // find the middle
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode right = slow.next;
        slow.next = null;                             // cut into two chains
        return merge(mergeSort(head), mergeSort(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; }   // ties take the left: stable
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = (a != null) ? a : b;              // glue the rest in one move
        return dummy.next;
    }
}

How long it takes: there are log n levels of halving, and each level merges n boxes, so O(n log n) every time. Extra room: only the recursion, O(log n). A bottom up version that merges runs of 1, 2, 4, and so on with a loop needs O(1).

Watch out for

• Quicksort on a list with a first or last pivot meets O(n^2) on sorted input, which is very common in real data. Many list quicksort codes online also crash on exactly that input when a partition range becomes empty.
• "Merge sort uses O(n) space" is true for arrays, not for lists. On lists only the recursion uses room.
• Do not say quicksort is always faster. Its worst case is O(n^2); it is fast in practice because of cache friendliness and small constants.

What interviewers ask next

• What does Java use? Arrays.sort on primitives is a dual pivot quicksort. Arrays.sort on objects and Collections.sort use TimSort, a merge based sort, because it is stable. Collections.sort on a LinkedList copies it into an array first.
• Can you make quicksort safe from the worst case? Pick a random pivot, or use introsort: quicksort that switches to heap sort if the recursion gets too deep. C++ std::sort does this.
• When would you use merge sort on arrays? When stability matters, when data is too big for memory (external sorting merges sorted files), or when you need a guaranteed O(n log n).
• Can a linked list be sorted with O(1) extra room? Yes, bottom up merge sort.
• Why is cache friendliness a big deal? Reading the next array slot is often already in the fast memory near the processor. Following a list arrow can land anywhere in memory, which can be many times slower.

Remember this

Grown-up words: jumping to a locker by number is random access, the judge is the pivot, nearby lockers being quick to read is cache locality, keeping equal items in order is stability, and gluing two sorted chains is the merge step.