Floating Point Radix Sort

Floating point radix sort sorts floating point numbers by transforming their binary representation into an order-preserving integer form, then applying standard radix sort.

The main challenge is that IEEE floating point bit ordering does not match numeric ordering for negative values.

Problem

Given an array $A$ of floating point numbers (typically IEEE 754), sort the array in increasing order.

Idea

Each floating point number is represented as:

sign bit
exponent
mantissa

Direct bitwise comparison fails because:

negative numbers have sign bit 1
bitwise order places all negative numbers after positive numbers

To fix this, transform each number into a sortable integer key.

Transformation

Let $x$ be a floating point value interpreted as an unsigned integer bit pattern.

Define transformed key:

k(x) = \begin{cases} x \oplus \text{sign\_mask}, & \text{if sign bit is 0} \\ \sim x, & \text{if sign bit is 1} \end{cases}

where:

sign_mask flips the sign bit
$\sim x$ is bitwise complement

This ensures:

negative values map to smaller keys
ordering matches numeric comparison

Algorithm

float_radix_sort(A):
    convert each float to integer bits

    for each element:
        if sign bit is 0:
            key = bits XOR sign_mask
        else:
            key = bitwise NOT bits

    radix sort keys

    reverse transformation to recover floats

    return sorted array

Example

Consider:

A = [-3.5, 2.1, -1.0, 0.0]

After transformation:

negative numbers map to low integer range
positive numbers map to high range

After radix sorting and inverse mapping:

[-3.5, -1.0, 0.0, 2.1]

Correctness

The transformation maps floating point values to integers such that:

x_1 < x_2 \iff k(x_1) < k(x_2)

Thus sorting transformed keys yields the correct numeric order. Since radix sort preserves integer ordering exactly, the final result is sorted.

Complexity

Let:

$n$ be number of elements
$m$ be number of bytes per float (typically 4 or 8)

Time:

O(n \cdot m)

Space:

O(n)

Properties

property	value
stable	yes, if radix sort is stable
in place	no
comparison based	no
handles floats	yes

When to Use

Use floating point radix sort when:

sorting large arrays of floats
performance is critical
radix sort is already implemented

Avoid when:

small arrays
simplicity is preferred
non-IEEE formats are used

Implementation (Python)

import struct

def float_radix_sort(a):
    def float_to_int(x):
        bits = struct.unpack('>Q', struct.pack('>d', x))[0]
        if (bits >> 63) == 0:
            return bits ^ (1 << 63)
        else:
            return ~bits & ((1 << 64) - 1)

    def int_to_float(x):
        if (x >> 63) == 1:
            bits = x ^ (1 << 63)
        else:
            bits = ~x & ((1 << 64) - 1)
        return struct.unpack('>d', struct.pack('>Q', bits))[0]

    keys = [float_to_int(x) for x in a]
    keys = sorted(keys)  # replace with radix sort if needed
    return [int_to_float(k) for k in keys]