A latency review flags Arrays.sort(orders, Comparator.comparing(Order::createdAt)) on a hot path. Someone comments “quicksort — shuffle first so we don’t hit the quadratic case,” and adds Collections.shuffle(orders) before the sort. The array is Order[]. Java did not run textbook quicksort. The shuffle destroyed the timestamp runs Timsort would have merged for almost free.
Object Arrays.sort and Collections.sort run Timsort: natural runs, insertion on short runs, then merge. Call the JDK. Do not hand-roll it. Primitive arrays are a different procedure.
This post is what that object sort actually does. Families and the catalog live on the Algorithms Roadmap. The loops you should not ship are already named; here we care about runs, why insertion appears inside the sort, and which overload you are calling.
Objects are Timsort; primitives are not
Arrays.sort is not one algorithm. The overload decides the procedure:
| Call | What Java runs |
|---|---|
Arrays.sort(Object[]) / List.sort / Collections.sort | Timsort — stable, adaptive |
Arrays.sort(int[]) and other primitive arrays | Dual-pivot quicksort — Quicksort owns that policy |
The comment on the hot path mixed the two. Shuffling an Order[] is a primitive-quicksort superstition applied to the object overload. You paid a full random permutation to “protect” a sort that wanted the existing order.
Timsort was written for real data: logs, timestamps, already-grouped keys, a list that was sorted yesterday and received a few inserts. It looks for that leftover order instead of pretending every input is random.
Note: Arrays.parallelSort on objects is a different fork (a parallel merge). This post is the sequential object Arrays.sort you already call.
Natural runs
A run is a maximal slice that is already in order. Left to right, Timsort records each non-decreasing stretch. A strictly decreasing stretch is a run too: reverse it in place and it becomes ascending. Equals break a descending run on purpose — reversing a plateau would reorder equal keys and lose stability.
createdAt (minutes), as filed:
[9:01, 9:02, 9:03, 8:50, 8:51, 9:10, 9:11]
0 1 2 3 4 5 6
runs:
R1 [9:01, 9:02, 9:03] ascending, stops at 8:50
R2 [8:50, 8:51, 9:10, 9:11] ascending to the endTwo runs, not seven random keys. A merge of two sorted slices is the cheap combine; you do not re-sort each slice from scratch. If the whole array is already ordered, there is one run and the merge step has nothing to do.
Short runs are grown by insertion up to a small floor (32 in OpenJDK) so later merges stay balanced. An Order[] shorter than that floor never reaches merge at all — the whole call is insertion. That is the whole reason the quadratic post still matters: insertion is cheap on a slice of length 32, and it is the wrong default on the whole export.
A walk: three runs, then merge
Toy input, toy floor. Values only, so the merge is readable. Treat min-run as 3: every run here is already long enough, so insertion has no extra keys to swallow.
a = [2, 5, 8, 1, 4, 7, 0, 3, 6]
0 1 2 3 4 5 6 7 8
identify runs (non-decreasing):
R1 [2, 5, 8] ends when 8 > 1
R2 [1, 4, 7] ends when 7 > 0
R3 [0, 3, 6]
merge R1 and R2 (stable: take from the left run on equals):
[2, 5, 8] + [1, 4, 7] → [1, 2, 4, 5, 7, 8]
merge that result with R3:
[1, 2, 4, 5, 7, 8] + [0, 3, 6] → [0, 1, 2, 3, 4, 5, 6, 7, 8]If the input had been [0, 1, 2, 3, 4, 5, 6, 7, 8], Timsort would have seen one run and stopped after the scan. If it had been reverse-sorted and strictly decreasing, one reverse would have produced that same single run.
The production Order[] is the first picture: mostly chronological, a backfill in the middle. Two or three runs plus a merge. The shuffled Order[] is the worst picture: runs of length one, insertion padding, then a full merge tree — still O(n log n), but you threw away the gift.
Merges are not “always the next two runs, left to right, no policy.” Timsort keeps a small stack of run lengths and merges when the sizes would otherwise get lopsided, so the combine tree stays balanced. When one run wins many comparisons in a row (a long timestamp stretch against a short backfill), it gallops: binary-search into the other run instead of walking it one key at a time. Both are why a from-scratch merge of R1 then R2 then R3 is the idea, not the implementation.
A descending walk, for the reverse rule:
a = [9, 6, 3, 1, 2, 5]
strictly decreasing from 9 to 1, then 2 > 1:
reverse [9, 6, 3, 1] → [1, 3, 6, 9]
leftover run → [2, 5]
merge → [1, 2, 3, 5, 6, 9]Do not reverse a non-increasing slice that contains equals. [3, 3, 2] is not a descending run; treating it as one and reversing would put the two 3s in the wrong relative order.
Why insertion is inside it
A run of length 2 does not need a general merge. Insertion slides a handful of keys into a tiny sorted prefix. Timsort does that on every short run, including a tiny array that never reaches the merge stage at all.
The idea, not a sort you ship: a run is a maximal non-decreasing slice.
static int runLimit(long[] createdAt, int lo) {
int hi = lo + 1;
int n = createdAt.length;
if (hi == n) {
return n;
}
if (createdAt[lo] <= createdAt[hi]) {
while (hi < n && createdAt[hi - 1] <= createdAt[hi]) {
hi++;
}
} else {
while (hi < n && createdAt[hi - 1] > createdAt[hi]) {
hi++;
}
// strictly decreasing: reverse createdAt[lo .. hi) in place
}
return hi;
}That helper is literacy. It is not Timsort. OpenJDK still has to pick a min-run, keep a stack of run lengths so merges stay balanced, gallop when one run wins many times, and allocate a temp slice for the merge. You will get those details wrong. The JDK already has them right.
Do not hand-roll Timsort. The hub named this cargo-cult next to gzip and Raft. Object Arrays.sort is Timsort.
Complexity
Adaptive means leftover order changes the bill. Worst case is still a full merge tree. Best case is a single run: count the array, notice it is already ordered, return.
| Time (worst) | O(n log n) |
| Time (already sorted / one run) | O(n) |
| Extra space | A temp buffer for merges; not in-place |
| Stable | Yes — equal keys keep their original relative order |
| In-place | No |
Compare that to shuffling first: you forced the worst shape of runs, then paid the n log n merge anyway, plus the shuffle. Compare it to a hand-rolled quadratic sort on the same Order[]: correct on forty rows, hostile at four hundred thousand.
Note: Stability is why the object overload is Timsort and the int[] overload is allowed to be quicksort. Primitive keys have no “original relative order” beyond the value itself. Order with equal timestamps does.
When not to hand-roll this
Skip a custom Timsort, and skip this procedure as a story you reimplement, when:
- You are sorting objects in process. Call
Arrays.sort/List.sort. There is no production reason to copy OpenJDK’sTimSort.javainto the service. - The array is primitives.
Arrays.sort(int[])is dual-pivot quicksort. Do not comment it as Timsort, and do not shuffle anObject[]because a quicksort lecture told you to. The quicksort post owns the pivot policy. - The file does not fit in RAM. Timsort needs the whole collection in memory plus a merge buffer. That later job is external (k-way) sort.
- You need the leftover order preserved as runs you own. If the product is “keep this list sorted while inserts arrive,” a tree is a layout, not a sort you re-run.
A nightly job that sorts yesterday’s Order[] by createdAt is exactly Arrays.sort. A comment that says “Timsort” is optional literacy. A class named CompanyTimsort is not.
JDK: Arrays.sort and List.sort
The hub’s default: sorted object arrays / lists → Arrays.sort / List.sort (Timsort). Call it. Pass the comparator you mean.
record Order(String id, long createdAt) {}
void sortByCreatedAt(Order[] orders) {
Arrays.sort(orders, Comparator.comparingLong(Order::createdAt));
}
void sortByCreatedAt(List<Order> orders) {
orders.sort(Comparator.comparingLong(Order::createdAt));
}Collections.sort(list) is list.sort(...). On an ArrayList that is the same object-array Timsort. On a LinkedList the implementation copies to an array, sorts, and copies back — a layout cost, not a reason to avoid the name.
Primitive contrast, so the hot-path comment does not come back:
int[] ids = {9, 1, 4, 0, 3};
Arrays.sort(ids); // dual-pivot quicksort, not TimsortRange overloads take fromIndex / toIndex (half-open) and sort only that slice. Useful when the live prefix of a capacity array is the data and the tail is garbage.
Do not reach for a PriorityQueue to “sort.” Dumping into a heap and polling is heapsort-shaped and not stable. Do not copy into a TreeSet unless you wanted a set. Do not shuffle first.
Cheat sheet
Job: sort object arrays / lists in memory
What it is: detect natural runs, insertion on short runs, merge
Objects: Arrays.sort / List.sort / Collections.sort → Timsort
Primitives: Arrays.sort(int[]) → dual-pivot quicksort
Best case: O(n) when the input is already one run
Worst: O(n log n)
Stable: yes on objects
Do not: hand-roll Timsort; shuffle objects "for quicksort"
Insertion: lives on short runs — see quadratic sorts
JDK: Arrays.sort(orders, comparator)Do:
- Call
Arrays.sort/List.sorton objects and leave leftover order alone. - Use a comparator that matches the order you want (timestamp, then id if ties must be deterministic).
- Remember insertion is inside Timsort for short runs, not a replacement for this call.
Don’t:
- Shuffle an
Object[]to “avoid quadratic quicksort.” - Comment primitive
Arrays.sortas Timsort, or objectArrays.sortas textbook quicksort. - Paste a from-scratch run/merge implementation into the service. The JDK already is that implementation.
Wrap-up
Object Arrays.sort is Timsort: find the runs that are already sorted, insertion-sort the short ones, merge the rest. Equal keys keep their order. Already-ordered input is a scan. The shuffle-before-sort comment was a different overload’s folklore. Primitive arrays run dual-pivot quicksort; that pivot policy is a later post. Insertion is inside this sort because short runs are the quadratic case that is still cheap — not because you should sort the invoice file with a nested loop.
Call the JDK. When the collection no longer fits in RAM, the procedure changes.