BrewlearnHow Java sorts
Dual-pivot quicksort for primitives, TimSort (stable) for objects.
Two algorithms, one name
Arrays of primitives (int[], double[]...) are sorted with dual-pivot quicksort: very fast, not stable. Arrays of objects (String[], Integer[]...) and List.sort use TimSort: stable, O(n log n) in the worst case.
int[] nums = {3, 1, 2};
Arrays.sort(nums); // dual-pivot quicksort
String[] words = {"b", "a"};
Arrays.sort(words); // TimSort
list.sort(null); // TimSort, natural orderWhy primitives may be unstable
Two equal ints are indistinguishable: there's no "original order" anyone could observe, so Java can use the faster unstable algorithm. Objects are different: two people can both be 30 but have different names, and callers may rely on their order. So objects get a stable sort.
Stable in action
Sorting by age only. What does this print?
record P(String name, int age) {}
void main() {
var ps = new ArrayList<>(List.of(
new P("Mia", 40), new P("Ann", 22),
new P("Leo", 22), new P("Kai", 40)));
ps.sort(Comparator.comparingInt(P::age));
for (P p : ps) IO.print(p.name() + " ");
}Ann Leo Mia KaiAnn Leo Kai MiaLeo Ann Mia Kai
Show the answer
Ann and Leo (22) come first, then Mia and Kai (40). Within each age, List.sort is stable, so names keep their original order: Ann before Leo, Mia before Kai.
TimSort's trick
Real data is often partly sorted. TimSort finds existing sorted runs, extends short ones with insertion sort, and merges runs like merge sort. On already sorted input it does about n comparisons; its worst case is still O(n log n).
Two keys, two passes
You want employees by department, and by name within each department, using a stable single-key sort twice. Which key do you sort by first?
Think about it, then reveal the answer
Sort by name first, then by department. The last sort decides the primary order, and stability keeps the earlier name order within each department. In real code, do it in one pass: Comparator.comparing(Emp::dept).thenComparing(Emp::name).
No Comparator for int[]
This is a compile error. The Comparator overloads take T[], and generics can't use primitive types, so there's no Comparator<int>. Sort ascending and reverse it, or use an Integer[].
int[] a = {3, 1, 2};
Arrays.sort(a, Comparator.reverseOrder());
// error: no suitable method foundWhy it matters at work
Stability is why sorting a table by one column, then another, behaves predictably in UIs. Knowing that List.sort is stable and O(n log n) lets you rely on it; knowing primitives use quicksort explains why there's no comparator overload for int[].
Key takeaways
- int[], double[]…: dual-pivot quicksort (not stable)
- Object[] and List.sort: TimSort (stable)
- TimSort finds existing sorted runs and merges them
- Stability lets you sort by one key, then by another
💡 TimSort is a librarian who notices shelves already in order and only merges them.
Tim Peters created TimSort for Python in 2002, and Java adopted it for objects in Java 7. In 2015, researchers using formal verification found a bug in TimSort in both Java and Python.
Practice questions
What does this print?
record P(String name, int age) {}
void main() {
var ps = new ArrayList<>(List.of(
new P("Zed", 30), new P("Amy", 25),
new P("Bob", 30)));
ps.sort(Comparator.comparingInt(P::age));
for (P p : ps) IO.print(p.name() + " ");
}- Amy Bob Zed
- Amy Zed Bob
- Zed Bob Amy
- Bob Zed Amy
Check your answer
Amy Zed Bob. Amy (25) comes first. Zed and Bob are both 30, and TimSort is stable, so they keep their original order: Zed before Bob.
Which algorithm does Arrays.sort(String[]) use?
- Dual-pivot quicksort
- TimSort
- Heap sort
- Bubble sort
Check your answer
TimSort. Object arrays use TimSort, which is stable and adapts to existing runs. Only primitive arrays use dual-pivot quicksort.