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
groupedbuffer — 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 forT[]) — 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 aToIntFunction<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_SIZEbased 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.
Top comments (0)