# Floating Point Radix Sort

# 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

```text id="f3k9qp"
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)

```python id="p2q7mx"
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]
```