↩ back to Non-Comparison Sorts
A ninth non-comparison sort, and a genuine combination of two already on this site rather than a new idea from scratch. Counting sort turns exact occurrence counts into exact final positions via a prefix sum, but only works when keys are integers it can index directly. Bucket sort handles continuous real-valued keys by scaling each one into a bucket with an arithmetic formula, but then needs a separate list per bucket and a real comparison sort to finish each one off. Proxmap sort (Fabri, 1990s — short for "proximity map") takes bucket sort's arithmetic mapping and feeds it through counting sort's own trick: count how many values land in each bucket first, turn those counts into exact starting offsets with a prefix sum, and every element's final resting range is fixed before a single value is placed. What's left for each element is a small insertion step — but confined entirely to its own bucket's few-slot window in one shared output array, never touching any other bucket, and never needing a separate list allocated for each one.
Enter a comma-separated list of real numbers, each in [0, 1) (this demo caps it at
16 values) — the default below is the exact same input bucket sort's own demo uses, so the two can be compared
directly on identical data. Step through three phases: counting how many values map
to each of k buckets via floor(value × k), turning those counts into
each bucket's fixed start index with a prefix sum, then placing
each element straight into the single output array — sliding it past any larger value already
sitting in its own bucket's window, and no one else's.
Three passes. First, count: walk the input once, and for each value v
compute b = floor(v × k) — this demo always sets k equal to the array
length, the same convention bucket sort's own demo uses — and increment hitCount[b].
Purely arithmetic, no comparisons, identical in spirit to bucket sort's own distribution step.
Second, map: turn those raw counts into a running total via an exclusive
prefix sum, so proxMap[b] means "how many values landed in buckets before b"
— exactly the one-past-the-end boundary of bucket b−1, and exactly the first free
slot bucket b owns. This is the same prefix-sum move counting sort's own "why it works" section
makes over exact integer keys; here it runs over arithmetic buckets instead, which is what makes it
compatible with bucket sort's continuous-key case at all.
Third, place: walk the input a second time. For value v in bucket
b, a locator[b] pointer (initialized to proxMap[b]) tracks the
next open slot inside that bucket's window. Naively writing v there and moving on would
group bucket b's values together correctly — but not necessarily in order relative to
each other, since a bucket can hold several values and the map function only promises they belong in
the same range, not which one is smaller (see Pitfalls). So instead, v is inserted: walk
backward from locator[b], shifting any already-placed value in this same window that's
bigger than v one slot to the right, and drop v into the gap. The shifting
never crosses proxMap[b] — the fixed left edge of this bucket's own window, established
before placement even started — so it can never disturb a slot that belongs to a different bucket.
That's the whole reason the boundary has to be computed before any placement happens: every
bucket's territory is claimed in advance, and the small insertion sort each one runs is provably
contained inside territory nothing else will ever touch.
The result reads like counting sort's exact single-pass placement and bucket sort's per-bucket insertion sort at the same time, because it genuinely is both — just with the per-bucket lists collapsed into disjoint windows of one shared array instead of separately allocated, and the placement done by insertion rather than append-then-sort.
One more detail matters for equal keys: the insertion-shift only moves a placed value when it's
strictly bigger than the one being inserted (>, never
>=), so two equal values already sharing a bucket are never shifted past each other
— whichever arrived first in the input keeps the earlier slot. That makes this implementation
stable, verified directly across 5,000 random trials with deliberately coarse, tie-heavy keys, zero
order violations.
Assumes every input value is in [0, 1), the same convention bucket sort's own
reference implementation uses. This is the exact scheme the demo above steps through, verified
against Array.prototype.sort across 20,000 random trials with zero mismatches:
function proxmapSort(arr) {
const n = arr.length;
if (n === 0) return [];
const k = n; // one bucket per element
const mapOf = v => Math.min(Math.floor(v * k), k - 1); // guard v === 1 exactly
const hitCount = new Array(k).fill(0);
for (const v of arr) hitCount[mapOf(v)]++; // count
const proxMap = new Array(k).fill(0); // map: exclusive prefix sum
for (let i = 1; i < k; i++) {
proxMap[i] = proxMap[i - 1] + hitCount[i - 1];
}
const locator = proxMap.slice(); // next open slot per bucket
const output = new Array(n).fill(null);
for (const v of arr) { // place
const b = mapOf(v);
let pos = locator[b];
while (pos > proxMap[b] && output[pos - 1] > v) { // insert within this bucket's window only
output[pos] = output[pos - 1];
pos--;
}
output[pos] = v;
locator[b]++;
}
return output;
}Skipping the in-window insertion leaves buckets grouped but not sorted. It's
tempting to treat locator[b] as a plain append pointer — write v at
locator[b] and move on, the way bucket sort's own distribution pass just appends to a
list. On the demo's own default input, values 0.44 and 0.42 both map to
bucket 4; appending without checking order places 0.44 first (it appears first in the
input) and 0.42 right after it, leaving that pair of output slots reading
0.44, 0.42 — backwards. Checked directly, not just on this one case: across 20,000
random trials, this broken variant produced a wrong final order in 18,711 of them
(93.6%) — it only ever gets lucky when every value in a bucket happens to already arrive in
the input in ascending order, which very rarely holds for more than a one-element bucket. Nothing
about this variant crashes or looks obviously broken; the values are still in the right
bucket, which is exactly why it's easy to miss without checking the output is actually
sorted.
The uniformity assumption is the same one bucket sort, Flash Sort, and Spreadsort all
share — and proxmap sort doesn't escape it either. Measured directly with the identical
construction those three pages already use: n = 200 values, k = 200
buckets, insertion-shift comparisons counted for real. Uniformly random values over [0, 1)
average 90.4 comparisons across 300 trials. The same 200 values drawn from the
narrow range [0.50, 0.51) instead collapse into a handful of buckets — one holding over
a hundred elements in a typical run — for an average of 5,152.1 comparisons, roughly
57× more work sorting the same count of values. The output is still correctly
sorted either time; the cost just falls entirely on whichever bucket's window absorbed everything, the
insertion-shift inside it degrading toward plain insertion sort's own O(n²)
worst case.
Getting the prefix sum's boundary off by one doesn't just misorder — it silently drops
data. Counting sort's own pitfalls note that scanning its placement pass in the wrong
direction breaks stability but still produces a correctly sorted array. Proxmap sort has no
equivalent safety net for its own boundary computation: computing proxMap as an
inclusive prefix sum (each bucket's own one-past-the-end index) instead of the correct
exclusive one (each bucket's start index) shifts every bucket's window one bucket's width too far
right. Run on this page's own demo array, bucket 4 (holding 0.44 and 0.42)
gets handed the boundary that actually belongs to bucket 5 — so its first element overwrites a slot
that bucket 6 needed, and its locator eventually walks off the end of the array
entirely, silently discarding whichever write doesn't fit. On this exact input the result is two
output slots that never get written at all and two input values — 0.44 and
0.91 — that vanish from the output completely, not merely out of order. Measured across
20,000 random trials: every single one produced a wrong result, and every single one
left at least one output slot permanently null. This is a sharper failure than the
uniformity pitfall above — not "slow on bad input," but silent data loss on every input, because the
whole in-window insertion depends on knowing exactly where a bucket's territory starts.
Time: O(n+k) expected when keys are uniformly distributed and
k is chosen proportional to n (this demo always sets k = n) —
one pass to count (O(n)), one pass to compute the prefix sum (O(k)), one
pass to place, each element's insertion-shift costing expected O(1) when its bucket's
window stays small (O(n) total) — the same balls-into-bins argument bucket sort's own "why it works" section makes.
Worst case O(n²) when the mapping collapses most values into one bucket's window,
exactly the second Pitfall above, measured for real rather than just asserted.
Space: O(n+k) — but with a smaller constant than bucket sort's own
O(n+k): hitCount, proxMap, and locator are three
plain O(k) integer arrays, and the single output array holds every element
exactly once (O(n)), rather than bucket sort's k separately allocated
per-bucket lists holding the same n elements split across them. That's the actual trade
this technique makes against its nearest sibling: identical time complexity and the identical
uniformity weakness, for one contiguous array instead of many small ones.
See Choosing a Non-Comparison Sort for how this compares against the site's other nine Non-Comparison Sorts entries — short version: reach for this over bucket sort when the values are continuous and roughly uniform but the per-bucket list overhead isn't worth paying, and over counting sort when the keys aren't small integers to begin with.