Bypassing Array.prototype.sort() with IEEE 754 Bit-Transforms

The default sort is fundamentally wrong for numbers

Array.prototype.sort() was designed for general-purpose sorting. It sorts strings, objects, mixed arrays, sparse arrays, and arrays with holes. This generality comes at a cost that is invisible on small datasets and catastrophic on large ones.

Three architectural decisions in the specification make it structurally unsuitable for high-performance numerical sorting.

Decision 1: String coercion by default

The ECMAScript specification (Section 23.1.3.30.2) states: "If comparefn is undefined, let x and y be the result of ToString." Without a comparator, every element is converted to a string before comparison.

[10, 9, 1, 2].sort();
// Result: [1, 10, 2, 9]
// Lexicographic: "1" < "10" < "2" < "9"

The ToString operation on a number is not a simple cast. It invokes the Number-to-String conversion algorithm, which handles special cases (negative zero, Infinity, NaN, scientific notation thresholds), allocates a heap string, and writes the character representation. For 10 million elements, that is 10 million string allocations on the JavaScript heap.

Each string comparison then proceeds byte-by-byte, with variable-length strings requiring length checks. A 7-digit number ("1234567") requires 7 byte comparisons in the best case and 14 in the worst (comparing two 7-digit numbers that differ only in the last digit).

Decision 2: Comparator callbacks

The workaround is a numeric comparator:

data.sort((a, b) => a - b);

This eliminates string coercion but introduces callback overhead. V8's TimSort calls the comparator for every comparison. TimSort performs approximately n * log2(n) comparisons in the average case.

For 1 million elements: 20 million comparator invocations. For 10 million elements: 230 million comparator invocations.

Each invocation crosses the native-to-JavaScript boundary. V8 must push a stack frame, marshal two arguments as tagged JavaScript values, execute the subtraction, unbox the return value to a native comparison result, and pop the frame. TurboFan (V8's optimizing compiler) can inline simple comparators, but inlining is not guaranteed for closures, polymorphic call sites, or comparators that capture external state.

Even with perfect inlining, 230 million function invocations have a fixed cost. The call/return overhead per invocation is approximately 2 to 5 nanoseconds on modern hardware. At 3 ns average: 230 million * 3 ns = 690 ms. That is the overhead alone, before any actual comparison logic.

Decision 3: Single-threaded, single-algorithm

Array.prototype.sort() runs on the main thread. It cannot dispatch to Web Workers. It cannot dispatch to the GPU. It uses one algorithm (TimSort in V8, merge sort in SpiderMonkey) regardless of data type, dataset size, or hardware capabilities.

TimSort is a hybrid merge-insertion sort optimized for partially sorted data. It detects natural runs, gallops through ordered segments, and merges with a stable algorithm. These are valuable properties for general-purpose sorting of mixed data. For uniformly random numerical data (the common case in analytics and data processing), the run detection is wasted work, the galloping heuristic fails and falls back to linear merge, and the O(n/2) temporary buffer triggers GC pressure.

Our Adaptive Multi-Tier Sorting System

We built a sorting system that eliminates all three bottlenecks. No string coercion. No comparator callbacks. No single-thread constraint.

The system operates on the binary representation of IEEE 754 floats, transforms them into sort-order-preserving unsigned integers, and sorts using a non-comparison radix algorithm that distributes naturally across parallel hardware.

The four-layer architecture

Layer 1: Precision analysis. The Precision Sufficiency Analyser determines whether Float32 narrowing is safe for the dataset. If any value exceeds Float32's representable range or if precision loss would alter the sort order, the GPU tier is excluded.

Layer 2: IEEE 754 bit-transform. Every float is converted to a sort-order-preserving unsigned integer using the Herf (2001) two-operation bitwise transform.

Layer 3: Sort execution. On the CPU and Web Worker tiers, the transformed integers are sorted using a 4-pass LSD radix-256 sort (one pass per byte of a 32-bit integer). Each pass is O(n). On the GPU tier, a two-phase bitonic sort + rank merge operates on the transformed unsigned integers.

Layer 4: Adaptive dispatch. A seven-factor scoring model selects the optimal backend based on dataset size, data type, hardware classification, and runtime calibration: GPU compute for large datasets on capable hardware, Web Workers with SharedArrayBuffer for medium datasets, main-thread sorts (sorting networks, insertion sort) for small datasets.

The IEEE 754 float-to-unsigned-integer transform

The standard float-to-integer transform (Herf, 2001) exploits the bit layout of IEEE 754 single-precision floats:

Bit:  31   30........23   22.................0
      [S]  [EEEEEEEE]     [MMMMMMMMMMMMMMMMMMMMMMM]
      sign  exponent (8)   significand (23)

The value is (-1)^S * 2^(E-127) * 1.M for normal numbers.

The sorting problem with raw bit reinterpretation

If you reinterpret the 32 bits of a float as an unsigned integer, positive floats sort correctly. The exponent occupies bits 30 to 23, and larger exponents produce larger unsigned values. Within the same exponent, the significand provides fine ordering.

Negative floats break this. The sign bit (bit 31) is the most significant bit. Any negative float reinterpreted as unsigned appears larger than any positive float. Among themselves, negative floats sort in reverse: -1.0 has a smaller magnitude but a larger unsigned representation than -100.0.

Two bitwise operations fix everything (Herf, 2001)

Rule 1: Positive floats (sign bit = 0). Flip the sign bit by ORing with 0x80000000.

// Float: 0_EEEEEEE_MMMMMMMMMMMMMMMMMMMMMMM  (positive)
// After: 1_EEEEEEE_MMMMMMMMMMMMMMMMMMMMMMM
transformed = bits | 0x80000000;

This adds 2^31 to the unsigned representation of every positive float. All positive floats now occupy the upper half of unsigned integer space (0x80000000 to 0xFFFFFFFF). Their relative order is preserved: the OR operation adds the same constant to all of them.

Rule 2: Negative floats (sign bit = 1). Flip all 32 bits by bitwise NOT.

// Float: 1_EEEEEEE_MMMMMMMMMMMMMMMMMMMMMMM  (negative)
// After: 0_eeeeeee_mmmmmmmmmmmmmmmmmmmmmmm  (all bits inverted)
transformed = ~bits;

Bitwise NOT accomplishes two things. It clears the sign bit, placing all negative floats in the lower half of unsigned space (0x00000000 to 0x7FFFFFFF), below all positive floats. And it reverses the order among negatives: -100.0, which had the largest unsigned representation among negatives, now has the smallest. -0.001, which had the smallest, now has the largest among negatives.

Complete mapping

After the transform, unsigned integer space maps exactly to float total order:

0x00000000  ->  -Infinity    (smallest float)
0x00000001  ->  -MAX_FLOAT
   ...          (negative floats, ascending)
0x7FFFFFFE  ->  -MIN_SUBNORMAL
0x7FFFFFFF  ->  -0.0
0x80000000  ->  +0.0
0x80000001  ->  +MIN_SUBNORMAL
   ...          (positive floats, ascending)
0xFF7FFFFF  ->  +MAX_FLOAT
0xFF800000  ->  +Infinity    (largest float)

Every IEEE 754 float maps to a unique unsigned integer. The mapping preserves total order. Negative zero maps to 0x7FFFFFFF, positive zero to 0x80000000 (negative zero sorts immediately below positive zero, consistent with IEEE 754 totalOrder). Subnormals sort correctly. Infinities sort at the extremes.

NaN handling

NaN values have exponent 0xFF with a non-zero significand. After the transform, they map to unsigned integers above 0xFF800000 (above +Infinity). Our engine strips NaN values during the precision analysis pass before the transform. If the dataset contains NaN, they are removed, the valid subset is sorted, and NaN values are reinserted at a configurable position (start, end, or error). NaN never reaches the sort kernel.

The inverse transform

After sorting, the unsigned integers are converted back to floats:

function inverseTransform(bits) {
  if (bits & 0x80000000) {
    // Was positive: clear the flipped sign bit
    bits = bits ^ 0x80000000;
  } else {
    // Was negative: flip all bits back
    bits = ~bits;
  }
  // Reinterpret as Float32 via type-punning
  tempUint32[0] = bits >>> 0;
  return tempFloat32[0];
}

The tempUint32 and tempFloat32 are views over the same ArrayBuffer, providing zero-cost type reinterpretation. No parsing. No allocation. One memory read through a different view.

Radix-256 sort on transformed integers

With floats encoded as sort-order-preserving unsigned integers, we apply a 4-pass LSD (least-significant-digit) radix sort with base 256.

Why radix sort is O(n)

Comparison-based sorts have a proven lower bound of O(n log n) comparisons. They cannot be faster because they operate on relative ordering (is A less than B?), and the information gained per comparison is one bit.

Radix sort bypasses this bound by operating on absolute representation. It does not compare elements. It distributes them into buckets based on digit values. Each pass processes one digit position. For 32-bit integers with base 256 (8-bit digits), there are 4 digit positions. Each pass is O(n + k) where k is the base (256). Total: O(4 * (n + 256)) = O(n).

Single pass structure

Each of the 4 passes (processing byte 0 through byte 3, least significant first):

1. Histogram. Scan the array. Count how many elements have each byte value (0 to 255) at the current byte position. Produces a 256-entry count array. O(n).

2. Prefix sum. Compute the exclusive prefix sum of the counts. Entry i becomes the starting output index for all elements with byte value i. O(256).

3. Scatter. Scan the array again. For each element, read its byte value, write the element to the output at the position indicated by the prefix sum, and increment the position counter. O(n).

Each pass is stable: elements with the same byte value retain their relative order from the input. After 4 stable passes (LSB to MSB), the array is fully sorted.

Why base 256

Base 2 (1 bit per pass): 32 passes. Too many. The per-pass overhead (scanning the array twice) dominates.

Base 16 (4 bits per pass): 8 passes with a 16-entry histogram. The histogram is tiny (64 bytes), but 8 passes means 8 full scans of the data.

Base 256 (8 bits per pass): 4 passes with a 256-entry histogram (1 KB). The histogram fits in L1 cache on every CPU and in workgroup shared memory on every GPU. Four full scans of the data.

Base 65536 (16 bits per pass): 2 passes with a 65,536-entry histogram (256 KB). The histogram blows out L1 cache and causes thrashing. The reduced pass count does not compensate.

Base 256 is the empirical optimum across all hardware we have tested.

GPU execution: bitonic sort + rank merge

On the GPU tier, the system does not use radix sort. Instead, it employs a two-phase algorithm optimised for WebGPU's SIMT execution model:

Phase 1: Local bitonic sort

Each workgroup sorts a 256-element tile entirely within shared memory using a bitonic sorting network. The network is data-oblivious (the comparison pattern does not depend on the data), which means zero branch divergence across threads. All 128 compare-and-swap operations per step execute simultaneously. The tile never leaves shared memory between the 36 parallel steps required for 256 elements.

Phase 2: Global rank merge

The sorted tiles are merged into a fully sorted output using a parallel binary-search rank computation. Each element independently computes its final position by binary-searching its merge partner tile. An asymmetric search condition (strict less-than for left-tile elements, less-than-or-equal for right-tile elements) preserves sort stability without auxiliary storage.

For a detailed treatment of both phases, including WGSL kernel code, see our article on Array.prototype.sort() performance limits.

Pipeline structure

The GPU dispatches execute sequentially without intermediate CPU readback. The CPU uploads the bit-transformed data once and reads back the sorted result once. Total transfers: 2 (one upload, one readback), regardless of the number of internal merge rounds.

Performance: GPU vs. Web Workers vs. Array.prototype.sort()

Benchmarked on uniformly random Float32 data across 14 device configurations:

At 5 million elements on discrete GPU hardware, the GPU achieves a 1.45x speedup over the Web Worker parallel tier, consistent with the threshold documented in our patent filing (GB2606693.6). At 10 million elements, the advantage holds steady at 1.45x as both tiers scale linearly.

Below 200,000 elements, the CPU radix-256 sort is faster than the GPU bitonic-merge. The GPU's transfer overhead (buffer upload, shader dispatch, result readback) dominates at small sizes. The adaptive dispatch engine detects this via the hardware calibration ratio and routes to the Web Worker tier automatically.

The crossover point (where GPU matches CPU performance) varies by hardware:

• Discrete GPU (NVIDIA, 250+ GB/s VRAM bandwidth): ~200,000 elements
• Integrated GPU (Intel, 50 GB/s shared memory): ~800,000 elements
• Integrated GPU (Apple, 100 GB/s unified memory): ~500,000 elements

These thresholds are not hard-coded. They are derived from runtime microbenchmarks at session initialization. The engine probes navigator.gpu.requestAdapter(), runs memory bandwidth and dispatch overhead tests, and computes the calibration ratio that determines the crossover for each specific device.

Where this applies in your stack

Every data processing pipeline has a sort somewhere. Often multiple sorts.

Dashboard column sorting. User clicks a header. 500,000 rows sort by that column. TimSort: 45 ms (frozen UI). GPU bitonic-merge: 4.8 ms (instant).

Percentile computation. P50, P95, P99 require a sorted dataset. 5 million trace spans: TimSort takes 498 ms. GPU bitonic-merge: 34.2 ms.

Top-N extraction. Top 100 revenue accounts from 2 million records. Full sort + slice. TimSort: 190 ms. GPU bitonic-merge: 14 ms.

Deduplication. Sort, then linear scan for adjacent duplicates. The sort dominates the total cost.

Merge joins. Joining two sorted datasets. Sort both, then merge. Two sorts at GPU speed instead of two at TimSort speed.

In every case, the sort is infrastructure. It is not the feature. It is the cost of the feature. Making it 5.2x to 45.5x faster does not change what your application does. It changes whether your application responds in the same animation frame as the user's input.

Our innovations page details the patented sorting engine (GB2606693.6) and the broader adaptive compute platform that makes it possible.

The engineering principle

Array.prototype.sort() is a 230-million-callback, single-threaded, comparison-based, O(n log n) operation that does not know what type your data is and does not know what hardware your user has.

We replaced it with a zero-callback, multi-tier, non-comparison, O(n) operation that exploits the binary representation of IEEE 754 floats, distributes across GPU compute shaders or Web Workers based on measured hardware capability, and verifies numerical precision before dispatch.

The difference is not a tuning improvement. It is a different computational model. Comparison-based sorting has a proven O(n log n) lower bound. Radix sorting on typed data has no such bound. The bit-transform unlocks O(n) on the CPU tier by converting an ordering problem into a distribution problem. On the GPU tier, a two-phase bitonic sort and rank merge exploits massive parallelism across thousands of concurrent threads.

This is representative of how we build enterprise AI automation infrastructure. We do not optimize within the constraints of the default tool. We identify the constraint (comparison-based sorting, single-threaded execution, no hardware awareness), determine whether it is fundamental or incidental, and replace the incidental constraints with an architecture that exploits the actual capabilities of the hardware.