A billing job sorts a long[] of event timestamps before a merge. Events already arrive in time order, with a few late stragglers. Someone copied textbook Lomuto and always pivoted on the last slot. At noon the array is messy and the job finishes in a couple of hundred milliseconds. At 03:00 the stream is a clean increasing sequence. The same n that was fine at noon now peels one element per pass and the worker hits the timeout.
Nobody “wrote a bad array.” They ran a partition whose choice of pivot turns nearly ordered input into the worst case.
Partition around a pivot, recurse on both sides; the pivot policy is the algorithm. Fixed last element, random, median-of-three, and dual-pivot are not cosmetics on the same procedure. They change the bill. Families and the words this series will not re-teach live on the Algorithms Roadmap. Here we only care about one in-place partition, the policy that picks the pivot, and what Java actually runs.
Partition puts the pivot in its final slot
Pick a pivot value. Rearrange the range so everything that belongs on the left of that value sits on the left, everything that belongs on the right sits on the right, and the pivot occupies the slot it will keep in the sorted array. Recurse on the two sides. Do not include the pivot in either recursive call — it is already home.
That is the whole procedure. The sketch below is Lomuto: pivot in a[hi], a growing “less-or-equal” prefix, one swap at the end to plant the pivot. Hoare’s two-finger partition is a different loop with the same job. Neither is what the JDK runs on primitives. The walk is here so the policy section has a concrete partition to attack.
After partition, two facts stay true:
a[p]is in its sorted position.- Every index
< pis<= a[p], every index> pis>= a[p](Lomuto with<=).
You never compare a left-side value to a right-side value again. The work is the partition plus the two recursive ranges.
Note: Equal keys may move past each other. Quicksort is not stable. If two events share a timestamp and a later stage assumes arrival order, this partition already broke that assumption.
A walked pass: pivot last, plant 5
Six scores. Lomuto. Pivot is the last element.
a = [4, 1, 7, 3, 8, 5]
0 1 2 3 4 5
pivot = a[5] = 5
i = 0 (next slot for a value <= pivot)
j=0 4<=5 swap a[0] with a[0] [4, 1, 7, 3, 8, 5] i=1
j=1 1<=5 swap a[1] with a[1] [4, 1, 7, 3, 8, 5] i=2
j=2 7>5 skip
j=3 3<=5 swap a[2] with a[3] [4, 1, 3, 7, 8, 5] i=3
j=4 8>5 skip
swap pivot into i=3: [4, 1, 3, 5, 8, 7]
left [4,1,3] | 5 | right [8,7]5 is done. Recurse on [4, 1, 3] and [8, 7] with the same last-element rule. Left: pivot 3, partition yields [1, 3, 4] after the next plant. Right: pivot 7, one swap, [7, 8]. Concatenate: [1, 3, 4, 5, 7, 8].
The same policy on an already-sorted range is the 03:00 timeout:
a = [1, 2, 3, 4, 5] pivot always a[hi]
plant 5 → [1, 2, 3, 4 | 5] left n-1, right empty
plant 4 → [1, 2, 3 | 4, 5]
plant 3 → [1, 2 | 3, 4, 5]
... one element per pass, ~ n + (n-1) + … comparisonsSorted input plus a naive last-element pivot is the quadratic case. Production streams are often already ordered. That is not an exotic adversarial array. It is Tuesday.
The loop: Lomuto on a slice
The membership of each value is one comparison against the pivot. The sketch matches the walk. It is a teaching partition, not a production sort.
static void quickSort(int[] a) {
quickSort(a, 0, a.length - 1);
}
static void quickSort(int[] a, int lo, int hi) {
if (lo >= hi) {
return;
}
int p = partition(a, lo, hi);
quickSort(a, lo, p - 1);
quickSort(a, p + 1, hi);
}
static int partition(int[] a, int lo, int hi) {
int pivot = a[hi];
int i = lo;
for (int j = lo; j < hi; j++) {
if (a[j] <= pivot) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
}
}
int tmp = a[i];
a[i] = a[hi];
a[hi] = tmp;
return i;
}lo >= hi is the empty-or-singleton stop. The pivot index p is excluded from both calls. Recursion depth is the shape of the partition tree: balanced splits stay logarithmic; the sorted last-element case is a chain of length n.
Note: The array is rearranged in place. The call stack is still extra. A degenerate pivot policy is an O(n) stack as well as an O(n²) clock.
The pivot policy is the algorithm
The loop above is fixed. What you put in a[hi] before you run it is not.
| Policy | What you plant at hi | What it does to the sorted case |
|---|---|---|
| Last element | a[hi] as it sits | Worst case. The 03:00 stream. |
| Random | Swap a random index in [lo, hi] onto hi | Expected O(n log n). Unlucky still O(n²). |
| Median-of-three | Median of first, middle, last, then swap onto hi | Kills sorted and reverse-sorted. Still attackable. |
| Dual-pivot | Two pivots, three regions (< p1, between, > p2) | What OpenJDK uses on primitive Arrays.sort |
A textbook last-element Lomuto is a different algorithm from Arrays.sort on int[]. Copying the sketch into a service and calling the result “what Java does” is how the timeout ships.
Random is one swap before partition. Median-of-three is a few comparisons that make “already ordered” a good split instead of a chain:
static void plantMedianOfThree(int[] a, int lo, int hi) {
int mid = lo + (hi - lo) / 2;
if (a[lo] > a[mid]) { int t = a[lo]; a[lo] = a[mid]; a[mid] = t; }
if (a[lo] > a[hi]) { int t = a[lo]; a[lo] = a[hi]; a[hi] = t; }
if (a[mid] > a[hi]) { int t = a[mid]; a[mid] = a[hi]; a[hi] = t; }
int t = a[mid];
a[mid] = a[hi];
a[hi] = t;
}After those swaps, a[hi] is the median of first, middle, and last, and Lomuto proceeds as before. The middle of [1, 2, 3, 4, 5] is 3, not 5. Dual-pivot is a different partition, not Lomuto with two guesses. The JDK primitive path is Yaroslavskiy dual-pivot, with insertion-sort cutoffs on tiny slices — not the sketch in the previous section.
Duplicates are a policy problem too. A range of equal keys with <= still walks the whole slice and can unbalance. Dual-pivot (and 3-way / Dutch-flag partitions) exist because many production keys collide: status codes, bucket ids, truncated timestamps.
Merge sort pays an array; this pays the policy
Merge sort divides, sorts each half, and merges into extra storage. The merge is stable. The extra array is the bill you always pay. Worst case stays O(n log n) because the split does not depend on the data.
Quicksort’s split is the data. You save the extra array and you give up stability. Average O(n log n) if the policy keeps splits from going degenerate. Worst O(n²) if it does not. That is the trade, not a personality difference between two “n log n sorts.”
| Extra array | Stable | Worst case | |
|---|---|---|---|
| Merge sort | Yes | Yes | O(n log n) |
| Quicksort (this sketch) | No (stack aside) | No | O(n²) unless the policy saves you |
Use merge sort when equal keys must keep input order, or when you cannot tolerate a quadratic surprise. Use a quicksort policy when you want in-place partition and you have actually chosen one. Do not pick last-element because the textbook diagram was shorter.
Complexity
The comparisons are in partition. A balanced tree of splits is O(n log n): each level looks at every remaining element, and there are O(log n) levels. A chain of splits is O(n²). Extra memory is the stack, not a second copy of the range.
| Time (average, decent policy) | O(n log n) |
| Time (worst, naive pivot) | O(n²) |
| Extra space (average) | O(log n) stack |
| Extra space (worst) | O(n) stack |
| Stable | No |
| In-place | Yes — rearranges the array; stack is extra |
Shuffling before a last-element partition is a policy in disguise: you bought the random case with a linear Fisher–Yates pass. Collections.shuffle is that pass on a List. It does not make the sketch dual-pivot.
When not to use this sketch
Skip a hand-rolled last-element quicksort when:
- The input is sorted or nearly sorted. Time series, auto-increment ids, already-merged runs. Last-element pivot is the worst case. Change the policy or do not use this procedure.
- Equal keys must keep their input order. Not stable. Sort objects with the JDK (Timsort) or merge sort.
- You needed a guaranteed
O(n log n)and tiny extra memory. That later post is heapsort, not a hope that random pivot is lucky. nis tiny. Insertion on a handful of slots is the honest loop. Dual-pivot implementations already cut over to it.
Do not hand-roll Lomuto on the billing path and call it Arrays.sort. The JDK already picked a policy.
A parallel int[] of scores beside a String[] of ids is also the wrong layout for a primitive partition: the ints swap, the names do not. Pack them as objects and you are no longer on the primitive quicksort path.
JDK: Dual-Pivot on primitives, Timsort on objects
The hub’s default: primitive Arrays.sort is Dual-Pivot Quicksort. Object Arrays.sort and List.sort / Collections.sort are Timsort. Do not claim Java object sort is quicksort.
int[] scores = {4, 1, 7, 3, 8, 5};
Arrays.sort(scores); // Dual-Pivot Quicksort
Integer[] boxed = {4, 1, 7, 3, 8, 5};
Arrays.sort(boxed); // Timsort — not the primitive path
List<Event> events = new ArrayList<>(batch);
events.sort(Comparator.comparing(Event::timestamp)); // TimsortSame method name. Different algorithms. int[] has no object identity, so stability is not a customer of that overload. Event rows that share a timestamp do care; that is why the object path is Timsort.
Range overloads (fromIndex, toIndex) sort a slice. They do not change which algorithm you are on.
Note: There is no Quicksort class. You call Arrays.sort. You do not paste Lomuto into a shared util and then wonder why a sorted extract of ids is quadratic while int[] in the same JVM is not.
Hand-roll a partition only when the job is not “sort this array” — a 3-way split around a rank, a quickselect for a percentile, a teaching walk. Production sort of a primitive array is the JDK call.
Cheat sheet
Job: partition around a pivot, recurse on both sides
Invariant: after partition, a[p] is home; left <= pivot, right >= pivot
Policy: last | random | median-of-three | dual-pivot — this *is* the algorithm
Worst case: sorted / reverse-sorted + last-element pivot → O(n²)
Average: O(n log n) when splits stay balanced
Stable: no
In-place: yes (array); stack is extra
Vs merge: extra array + stable + guaranteed n log n
JDK ints: Arrays.sort → Dual-Pivot Quicksort (not Lomuto)
JDK objects: Arrays.sort / List.sort → Timsort (not quicksort)Do:
- Treat pivot policy as part of the algorithm, not a comment above
partition. - Call
Arrays.sorton the primitive array you actually have. - Reach for merge sort or Timsort when equal keys must keep order.
Don’t:
- Pivot on the last slot for a stream that is already ordered.
- Confuse primitive
Arrays.sort(dual-pivot) with objectArrays.sort(Timsort). - Copy textbook Lomuto into production and name it after the JDK.
Wrap-up
Quicksort is not “the fast n log n sort.” It is a partition that plants a pivot and recurses, and the way you choose that pivot decides whether a nearly sorted long[] is O(n log n) or a timeout. Last-element Lomuto is a teaching walk. Random and median-of-three are policies that make the usual production shapes safe in expectation. Dual-pivot is what primitive Arrays.sort actually runs. Object sort is Timsort. Merge sort pays an extra array and keeps equal keys in order. Pick the procedure that matches the array you have — then call the JDK unless the job is not a sort.