Partitioning and Sorting Arrays with Many Repeated Entries

The problem, simply

You get an array with lots of repeated numbers, for example a million numbers but only a handful of different values. Sort it fast.

Plain quicksort can get very slow here. The fix is to split the array into three parts around a chosen value, the pivot: smaller than the pivot, equal to it, and bigger than it. The equal part is already in its final place, so only the other two parts need more work.

A story to remember it

Picture it

Examples

Way 1: the simple way

Use plain quicksort with a two way split. Pick the last number as the pivot. Move everything smaller than or equal to it to the left, put the pivot after them, and sort both sides.

1. pivot = arr[hi], and i marks where the "small" part ends.
2. For each j from lo to hi - 1: if arr[j] <= pivot, swap it into the small part.
3. Put the pivot right after the small part, then sort the left side and the right side.

class Solution {
    public void sort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }

    private void quick(int[] arr, int lo, int hi) {
        if (lo >= hi) return;
        int pivot = arr[hi], i = lo;
        for (int j = lo; j < hi; j++) {
            if (arr[j] <= pivot) {            // equal numbers all go left
                int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
                i++;
            }
        }
        int t = arr[i]; arr[i] = arr[hi]; arr[hi] = t;   // pivot into place
        quick(arr, lo, i - 1);
        quick(arr, i + 1, hi);
    }
}

How long it takes: on random distinct numbers about O(n log n). But when many numbers are equal, all of them land on one side, so each split only removes one number. On [5, 5, 5, ..., 5] that is O(n^2). Extra room: the calls can go n deep, O(n), which can overflow the stack on big inputs.

Way 2: the clever way

Split into three parts in one pass, with three fingers:

• Everything left of lt is smaller than the pivot.
• Everything from lt to i - 1 equals the pivot.
• Everything from i to gt is not looked at yet.
• Everything right of gt is bigger than the pivot.

Look at arr[i]:

1. Smaller: swap it with arr[lt], then move both lt and i right.
2. Equal: just move i right.
3. Bigger: swap it with arr[gt] and move gt left. Do not move i, because the number that came from gt has not been looked at yet.

Stop when i passes gt. Then sort only lo..lt-1 and gt+1..hi.

class Solution {
    public void sort(int[] arr) {
        quick3(arr, 0, arr.length - 1);
    }

    private void quick3(int[] arr, int lo, int hi) {
        if (lo >= hi) return;
        int pivot = arr[lo + (hi - lo) / 2];
        int lt = lo, i = lo, gt = hi;
        while (i <= gt) {
            if (arr[i] < pivot) {
                swap(arr, lt++, i++);         // smaller: to the left part
            } else if (arr[i] > pivot) {
                swap(arr, i, gt--);           // bigger: to the right part, look at i again
            } else {
                i++;                          // equal: stays in the middle
            }
        }
        quick3(arr, lo, lt - 1);              // the equal part lt..gt is finished
        quick3(arr, gt + 1, hi);
    }

    private void swap(int[] arr, int a, int b) {
        int t = arr[a]; arr[a] = arr[b]; arr[b] = t;
    }
}

How long it takes: every split finishes one whole value, so with k different values and good pivots there are about log k levels of O(n) work, O(n log k). When all values are different that is the usual O(n log n), and when all are equal it is one pass, O(n). A bad pivot every time can still cause O(n^2), so real libraries pick the pivot at random. Extra room: the call depth, O(log n) with good pivots.

Watch out for

• The loop condition is i <= gt, not i < gt. The number at gt is also unseen.
• Recursing into lo..gt or lt..hi instead of skipping the equal part throws away the whole benefit.
• Picking the first or last number as the pivot makes already sorted input slow. The middle or a random one is safer.
• Quicksort is not stable: equal numbers may change their order. That only matters when they carry other data.

What interviewers ask next

• Sort an array of only 0s, 1s and 2s in one pass. That is this exact split with pivot 1, the Dutch national flag problem.
• If the values are small whole numbers, counting sort is O(n + range). Count each value, then write them back.
• If there are few distinct values but they are huge or not numbers, count them in a TreeMap, which costs O(n log k) and writes them back in order.
• Why does Java's Arrays.sort for int[] handle repeats well? It uses dual pivot quicksort, which also groups numbers equal to the pivots.
• Partition around a value without sorting, for example "all negatives first". That is one pass of the same three finger loop.

Remember this

Grown-up words: the three piles are three way partitioning, the chosen card is the pivot, the whole method is 3 way quicksort (Dijkstra's version), and the 0, 1, 2 case is the Dutch national flag problem.