I Built a Stable Sorting Algorithm That Beats Java's Dual-Pivot Quicksort and TimSort

Shreyas — Fri, 12 Jun 2026 09:38:33 +0000

Update: This post has been substantially revised from the original. Since first publishing, I re-tuned the algorithm's parameters through a proper JMH sweep, re-ran every benchmark on a single consistent machine, added an adversarial-input stress test, measured actual peak memory footprint (not just allocation rate), and added a full worked example below so you can trace exactly what the algorithm does by hand. The core idea is unchanged — the numbers and rigor behind them are not.

A while back I finished benchmarking something I've been building — a cache-aware, stable, histogram-based sorting algorithm I'm calling BusSort. The results still surprise me.

At 100 million elements, it runs up to 2.75x faster than Java's Dual-Pivot Quicksort on distribution-heavy int[] data — while being stable, which DPQ is not. The generic variant beats TimSort by up to 2.87x on random T[] data.

It also loses in a few honest, specific ways — on reverse-sorted input, and (for the generic variant) on nearly-sorted input. I'll show those numbers too, not just the wins.

The Problem With Quicksort at Scale

Quicksort-based algorithms partition elements with random writes across the entire array. At large scales this causes cache thrashing — elements get written to memory locations all over the place, constantly missing L1 and L2 cache.

The larger the array, the worse it gets.

The Core Idea

Instead of scattering elements globally, BusSort processes data in L1 cache-sized chunks — 4096 integers (~16KB) — using a histogram to know exactly where every element belongs before moving it.

For each chunk, it does 4 passes:

PASS 1 — Scan left-to-right, compute the bucket for each element, build a local histogram for this chunk only
PASS 2 — Compute local prefix sums (each bucket's position within the chunk)
PASS 3 — Scatter into a local grouped buffer — the "bus." Because this buffer is L1-sized, all random writes stay in cache ✅
PASS 4 — Copy each bucket's portion from the local buffer to its correct global position

After one pass, each bucket is recursed into using the same four passes, until a bucket is small enough to finish with insertion sort.

Walking Through It By Hand

Numbers alone don't build intuition, so here's the entire algorithm traced on a small array — every variable, every pass. To keep this on one page, I'm using small illustrative constants (BUCKETS=4, BUS_SIZE=8, THRESHOLD=5) instead of the real tuned values (256/4096/64) — the logic executed is identical either way, just at a size you can follow by hand.

Input (20 elements):

idx:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
val:  15  3  9  1 18  7 12  4 19  0 11  6 16  2  8 14  5 17 10 13

Level 1: the whole array

First, find min=0, max=19. Since min ≠ max, we distribute.

Bucket range: rangeL = (19-0+1+4-1)/4 = 22/4 = 5 — so bucket 0 covers values [0,4], bucket 1 covers [5,9], bucket 2 covers [10,14], bucket 3 covers [15,19].

Global histogram (one pass over all 20 elements, computing value/5 for each, capped at bucket 3):

globalCount = [5, 5, 5, 5] — exactly 5 elements per bucket, by construction of this example.

Prefix sums:

globalNext   = [0, 5, 10, 15]   (mutable — advances as chunks get written)
bucketStarts = [0, 5, 10, 15]   (frozen — used later to define each bucket's boundaries)

Now the chunk loop. With BUS_SIZE=8, 20 elements split into three chunks: [0-7], [8-15], [16-19].

Chunk 1 — indices 0-7: values 15,3,9,1,18,7,12,4 → buckets 3,0,1,0,3,1,2,0.

Pass 1 builds localCount = [3,2,1,2] (3 elements landed in bucket 0, 2 in bucket 1, 1 in bucket 2, 2 in bucket 3).

Pass 2 prefix-sums that into localStart = [0,3,5,6].

Pass 3 scatters into the local grouped buffer, respecting each element's original left-to-right position within its bucket:

grouped = [3, 1, 4, 9, 7, 12, 15, 18]

Look closely: bucket 0's slice is [3,1,4] — in the original array, these appeared at indices 1, 3, 7, in that order. They land in grouped in that same order. That's the entire stability mechanism, visible in one line.

Pass 4 copies each bucket's slice from grouped into the real output array at globalNext[b], then advances globalNext[b] by however many elements just got written:

bucket	count	written to output at	globalNext becomes
0	3	positions 0-2	0+3 = 3
1	2	positions 5-6	5+2 = 7
2	1	position 10	10+1 = 11
3	2	positions 15-16	15+2 = 17

Chunk 2 — indices 8-15: values 19,0,11,6,16,2,8,14 → buckets 3,0,2,1,3,0,1,2. Same four passes, localCount=[2,2,2,2]. After this chunk, globalNext = [5, 9, 13, 19].

Chunk 3 — indices 16-19: values 5,17,10,13 → buckets 1,3,2,2. localCount=[0,1,2,1] — bucket 0 gets nothing from this chunk, so its copy step is simply skipped. After this chunk, globalNext = [5, 10, 15, 20].

Output after level 1:

idx:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
val:  3  1  4  0  2  9  7  6  8  5 12 11 14 10 13 15 18 19 16 17

Every position filled exactly once — the three chunks' contributions to each bucket landed in separate, non-overlapping slices, in original left-to-right order.

Level 2: recurse into each bucket

Using the frozen bucketStarts = [0,5,10,15] (not the now-moved-on globalNext), the four buckets are [0-4], [5-9], [10-14], [15-19]:

Bucket 0: [3,1,4,0,2] — 5 elements, n ≤ THRESHOLD(5) → straight to insertion sort → [0,1,2,3,4]
Bucket 1: [9,7,6,8,5] → insertion sort → [5,6,7,8,9]
Bucket 2: [12,11,14,10,13] → insertion sort → [10,11,12,13,14]
Bucket 3: [15,18,19,16,17] → insertion sort → [15,16,17,18,19]

Final result:

idx:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
val:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19

Sorted. At production scale (BUCKETS=256, BUS_SIZE=4096, THRESHOLD=64), the mechanism is identical — just more buckets, bigger chunks, more insertion-sort headroom.

Benchmark Results

Machine: Intel Core i5-1035G1 @ 1.00GHz (4 cores / 8 threads), 8GB RAM | Java: 21
Methodology: JMH 1.37 — 5 warmup iterations, 10 measurement iterations, 3 JVM forks, -prof gc

`int[]` vs Dual-Pivot Quicksort (`n = 100,000,000`, tuned: BUCKETS=256, BUS_SIZE=4096, THRESHOLD=64)

Input Type	BusSort (ms)	DPQ (ms)	Ratio
Random	3981	10606	2.66x ✅
Duplicates	954	2622	2.75x ✅
Few Duplicates	2108	4113	1.95x ✅
Clustered	1897	2707	1.43x ✅
Nearly Sorted	3306	3783	1.14x ✅
Adversarial*	3725	3908	1.05x — near tie
Sorted	42	38	0.92x — trivial cost either way
All Same	42	38	0.89x — trivial cost either way
Reverse	333	111	0.33x ❌

`T[]` vs TimSort (`n = 10,000,000`, tuned: BUCKETS=80, BUS_SIZE=4096, THRESHOLD=64)

Sorting Record objects — an int key plus a field, not boxed Integer.

Input Type	BusSort (ms)	TimSort (ms)	Ratio
Random	1864	5346	2.87x ✅
Few Duplicates	1015	2135	2.10x ✅
Clustered	882	1478	1.68x ✅
Duplicates	998	1637	1.64x ✅
Adversarial*	1723	2093	1.21x ✅
All Same	19.8	22.5	1.14x — trivial cost either way
Sorted	22.5	21.7	0.96x — trivial cost either way
Reverse	185	104	0.56x ❌
Nearly Sorted	673	358	0.53x ❌

* Adversarial: 99% of elements packed into a 1000-wide key range, 1% spread across the full int range — deliberately stresses histogram skew. More on this below.

Full benchmark code, including this adversarial case, is in the benchmarks/ and generics/benchmarks/ folders.

The Adversarial Case

Bucket-based sorts don't get a free logarithmic recursion-depth guarantee the way balanced comparison sorts do — the split is data-dependent, not count-dependent. If a value distribution is skewed enough that most elements land in one bucket at every recursion level, depth can approach O(n) instead of O(log n), and the whole algorithm's total work approaches O(n²) — the same theoretical worst case Quicksort has always had.

I built a test specifically to stress this (99% of values crammed into a narrow range) rather than wait for someone else to find it. The result: BusSort's advantage collapses to roughly a tie for int[] (1.05x) under this skew, though it still holds a real edge for T[] (1.21x). It doesn't get worse than the JDK's own sort at the scales I tested — but the margin that makes it worth using elsewhere mostly disappears.

I deliberately haven't added a fallback mechanism into the algorithm itself — I wanted the core logic to stay simple and auditable, even at the cost of this one known weak spot. A natural fix would be a lightweight health-check after the histogram pass: if one bucket holds a disproportionate share of elements, hand that sub-range to Arrays.sort() instead of recursing further. I'd genuinely like input on whether that's worth building in, and what threshold would make sense.

Peak Memory — Not Just Allocation Rate

JMH's -prof gc reports cumulative allocation (bytes/op), which isn't the same as peak live memory at any instant — a more relevant number for a memory-conscious comparison. I measured this separately using MemoryPoolMXBean peak-usage tracking around a single sort call.

n	BusSort (`int[]`)	DPQ	BusSortGenerics	TimSort
1,000,000	13.1 MB	13.1 MB	36.4 MB	41.0 MB
10,000,000	121.1 MB	81.1 MB	350.1 MB	370.2 MB
100,000,000	1153.1 MB	769.1 MB	—	—

Two different stories here, worth stating plainly:

int[] vs DPQ: at scale, BusSort uses ~50% more peak memory than DPQ. Expected — DPQ sorts in-place, BusSort allocates a full auxiliary buffer every level. This is a genuine tradeoff: faster, but not free.
T[] vs TimSort: BusSortGenerics uses less peak memory than TimSort at every scale I measured. TimSort isn't in-place either — its merge machinery needs its own auxiliary array — so for the generic variant, BusSort wins on speed and memory.

Why It's Stable

Chunks are processed left-to-right, and within each chunk, elements are scattered left-to-right — globalNext[b] only ever advances, never resets, so earlier chunks always land before later chunks in the output. No index tagging, no extra bookkeeping. You can see this directly in the worked example above: bucket 0's elements landed in grouped in exactly the order they appeared in the original array.

For int[], equal integers are identical by value, so stability is technically unobservable — but the mechanism is identical for the generic variant, where it matters for real objects with equal keys.

Known Trade-offs

Reverse-sorted input is a real weak spot (0.33x for int[], 0.56x for T[]) — the reverse-detection path preserves stability for equal-key runs, which costs more than a simple swap-based reversal would. Known, understood, not fixed.
Nearly-sorted input, generic variant only (0.53x) — TimSort's run-detection is specifically built to exploit existing order and wins outright here. BusSort's histogram approach doesn't detect or exploit "already mostly sorted" at all, by design.
No pure Comparator<T> support — BusSortGenerics requires a ToIntFunction<T> numeric key extractor. Arithmetic bucketing needs a numeric key; comparison-based sorting doesn't.
Not in-place — see peak memory above.

What's Next

[x] Sequential parameter tuning via JMH (bucket count, chunk size, insertion-sort threshold)
[x] Adversarial-input stress testing
[x] GC pressure and peak-memory measurement
[ ] Health-check fallback for adversarial distribution collapse (documented above, not yet implemented — genuinely open, I'd like feedback on this one)
[ ] Dynamic stack sizing
[ ] Auto-tune BUS_SIZE based on runtime L1 cache size
[ ] Parallel / multi-threaded variant

GitHub

Full implementation, benchmarks (including the adversarial and peak-memory ones above), and the generic variant are all published.

👉 github.com/dev-shreyaspatil/BusSort

I'm sharing this as independent work, hoping for feedback and scrutiny from people who know sorting and the JVM better than I do. Curious what the Java community thinks — especially the adversarial-case fallback question above, and whether there's published cache-aware bucket/radix sort literature I should be comparing against.

DEV Community: Shreyas