↩ back to Non-Comparison Sorts
Flash Sort sits at a real intersection of two entries already on this site rather than being a
wholly new idea. Like bucket sort, it classifies every
value with one arithmetic formula instead of comparing values against each other — but where bucket
sort assumes keys already sit in [0, 1) and allocates a fresh array per bucket, Flash
Sort works over any numeric range (scaling by the array's own min and max) and permutes everything
in place, following the exact swap-chain-with-cursors technique
American flag sort uses for its own digit buckets.
The one thing Flash Sort's formula can't promise that a digit can is an *exact* boundary — two
values landing in the same class aren't necessarily equal, just close — so a single pass of plain
insertion sort over the now mostly-grouped array
finishes the job.
Enter a comma-separated list of integers, positive or negative (this demo caps it at 10 values).
Step through four phases: classifying each value into one of m classes
via floor((m-1) × (v-min) / (max-min)) — this demo always uses
m = max(2, floor(n/2)) — turning those counts into fixed start/end
boundaries per class, permuting the array in place so every class occupies its own
contiguous range (bordered bar is the index being examined, solid bar is its swap partner), then
finishing with one insertion-sort pass (the accent bar is the "hole" being carried
left, same convention as insertion sort's own demo) to
resolve whatever order survives within each class.
The classification formula floor((m-1) × (v-min) / (max-min)) is monotonic in
v: a larger value never lands in a smaller class. Counting how many values fall into
each class, then turning those counts into a running total (offset by 0, same running-total trick
American flag sort and
counting sort both use), fixes each class's final
[start, end) index range before anything moves — exactly what makes an in-place
permutation possible instead of needing a fresh output array per class the way bucket sort's own
demo does. The permutation itself reuses American flag sort's cursor-and-swap-chain exactly: walk
each class with a cursor starting at its own start; if the value there already belongs,
advance; otherwise swap it into its real class's cursor slot and advance that one instead,
without moving the current cursor — the value that just arrived might not belong there either, and
has to be checked again.
Where Flash Sort genuinely differs from American flag sort's digit buckets: a digit is exact
(everything in bucket 7 has digit 7, full stop), but a class computed from a continuous formula only
promises everything in class c is no larger than anything in class
c+1 — two values 41 and 49 can land in the same class despite being far apart
within it. That's why the permutation phase alone doesn't finish the sort: it groups the array into
m correctly-ordered blocks, but a block with more than one value can still hold them in
any order. Rather than recursing the way American flag sort recurses into the next digit, Flash Sort
finishes with a single flat insertion sort pass over
the whole array — safe because insertion sort is correct regardless of the input's starting
order, and cheap in practice because the permutation phase already did most of the work: with
m classes averaging n/m elements each, insertion sort only has to resolve
disorder within a class, not across the whole array.
m is fixed at max(2, floor(n/2)), matching the demo above exactly:
function classOf(v, min, max, m) {
if (max === min) return 0;
let c = Math.floor((m - 1) * (v - min) / (max - min));
if (c >= m) c = m - 1; // v === max lands exactly on the last class
return c;
}
function flashSort(a) {
const arr = a.slice();
const n = arr.length;
if (n <= 1) return arr;
const min = Math.min(...arr);
const max = Math.max(...arr);
if (min === max) return arr; // every value identical — already sorted
const m = Math.max(2, Math.floor(n / 2));
const counts = new Array(m).fill(0);
for (let i = 0; i < n; i++) counts[classOf(arr[i], min, max, m)]++;
const starts = new Array(m);
const ends = new Array(m);
let acc = 0;
for (let c = 0; c < m; c++) {
starts[c] = acc;
acc += counts[c];
ends[c] = acc; // exclusive
}
const next = starts.slice(); // per-class write cursor
for (let c = 0; c < m; c++) {
while (next[c] < ends[c]) {
const idx = next[c];
const d = classOf(arr[idx], min, max, m);
if (d === c) { next[c]++; continue; } // already in its class
[arr[idx], arr[next[d]]] = [arr[next[d]], arr[idx]]; // swap into its real class
next[d]++;
}
}
// classes are grouped in order but not internally sorted — finish with one pass
for (let i = 1; i < n; i++) {
const key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
arr[j + 1] = key;
}
return arr;
}Skipping the finishing insertion-sort pass leaves classes grouped but not sorted.
On this page's own default array ([42, -8, 91, 15, -30, 63, 27, 50], min -30, max 91,
m=4), the permutation phase alone produces
[-8, -30, 42, 15, 27, 50, 63, 91] — every value is in its correct class, but class
1 (42, 15, 27, 50) is left in whatever order the swap chain happened to leave it, and
class 0's two values are swapped relative to each other too. Checked broadly, not just this one
case: across 5,000 randomized trials (array sizes 5–24), stopping after the permutation phase
disagrees with a correct sort on 4,942 of them — 98.8%, not a rare edge case.
Reusing bucket sort's own floor(v × k) formula directly, without
rescaling by the array's own min and max first, doesn't produce a wrong answer — it silently
throws away the whole benefit of classifying at all. It's a tempting shortcut, since both
algorithms distribute by a formula rather than a digit. But bucket sort's formula assumes values
already live in [0, 1); feed it Flash Sort's actual value range (say, four-digit
numbers) and nearly every computed class index lands far outside [0, m-1]. Any index
outside that range never gets counted into a real class, so every one of that class's own
while (next[c] < ends[c])) loops in the permutation phase does nothing at all —
the array comes out of that phase completely untouched. Because the finishing insertion-sort pass
runs over the whole array regardless of how the permutation phase left it, the final result
is still correctly sorted — no crash, no wrong answer, nothing a correctness check would ever
catch. What's lost is silent: measured directly, at n=50 the broken version costs 11.4x
the finishing comparisons of the correctly-scaled version; growing to 19.1x at n=100,
41.0x at n=200, and 84.3x at n=400 — a widening gap with no visible
symptom, because the whole point of classifying first was to keep that finishing pass cheap, and a
class index nobody can ever land in accomplishes exactly nothing.
Time (average case), measured, not asserted: on uniformly random data with
m = n/2 classes, the finishing insertion sort's own comparison count grows close to
linearly with n — 27 at n=20, 145 at n=100, 738 at
n=500, 2,942 at n=2,000, 7,374 at n=5,000 (roughly
1.4–1.5× n throughout, nowhere near n log n's own reference
curve, let alone n²) — the real payoff of grouping first: most classes end
up small enough that the finishing pass barely has to shift anything, regardless of whether the
input started sorted, reverse-sorted, or random (all three land within a small constant factor of
each other at every size checked).
Time (worst case), also measured directly: that average-case bound depends on
values actually spreading across classes roughly evenly — the same uniformity assumption
bucket sort's own Pitfalls section names, since both
algorithms classify by the identical kind of formula. Force a skew (95% of a 500-element array
packed into one narrow 20-wide sub-range, a few outliers keeping min/max
wide) and comparisons jump to 54,197 against uniform random data's 735 at the same size — a
73.8× blowup, consistent with the n² collapse (62,500 ≈ n²/4) predicted
when nearly every value ends up fighting for space inside one oversized class. Space:
O(m) for the counts/starts/ends/cursor arrays (four values each), independent of
n — genuinely less than bucket sort's
own O(n+k), the same in-place trade American flag sort makes against
radix sort, paid for here by giving up stability and, per
the second Pitfall above, needing the classification formula scaled to the data's actual range.
See Choosing a Non-Comparison Sort for how this compares against the site's other nine Non-Comparison Sorts entries.