radixSortDouble function

void radixSortDouble(
  1. List<double> data, {
  2. bool ascending = true,
  3. bool reuseBuffer = true,
})

Sorts a list of doubles in place using a stable Radix Sort.

This implementation is optimized for 64-bit floating-point numbers (doubles). It works by reinterpreting the bits of IEEE-754 floats into a 64-bit integer representation that can be sorted lexicographically, which preserves the original floating-point order.

The sort is stable. It correctly handles positive and negative numbers, zero, -0.0, double.infinity, and double.negativeInfinity. double.nan values will be grouped together but their final position is not guaranteed.

Performance optimizations:

  • Zero-copy operations when input is already Float64List
  • Direct buffer manipulation without intermediate copies
  • Efficient descending sort without recursion
  • Optimized bit manipulation loops

Example:

final numbers = [10.5, -1.2, 900.0, -10.0, 0.0, 5.8];
radixSortDouble(numbers);
print(numbers); // [-10.0, -1.2, 0.0, 5.8, 10.5, 900.0]
  • data: The list of doubles to be sorted.
  • ascending: Sort order (true for ascending, false for descending).
  • reuseBuffer: If true, the auxiliary buffer used for sorting will be sourced from a global pool. This can significantly reduce garbage collection pressure and improve performance when sorting many lists of similar sizes.

Implementation

void radixSortDouble(
  List<double> data, {
  bool ascending = true,
  bool reuseBuffer = true,
}) {
  if (data.length < 2) {
    return;
  }

  final n = data.length;
  Float64List workingList;
  bool isDirectView = false;

  // Try to work directly with the buffer if data is already Float64List
  if (data is Float64List) {
    workingList = data;
    isDirectView = true;
  } else {
    // Need to create a copy
    workingList = Float64List(n);
    for (var i = 0; i < n; i++) {
      workingList[i] = data[i];
    }
  }

  // Create a Uint64List view on the same buffer to reinterpret the bits
  final unsignedView = Uint64List.view(
    workingList.buffer,
    workingList.offsetInBytes,
    n,
  );

  const signMask = 0x8000000000000000;

  // 1. Transform: Map floats to a sortable unsigned integer representation
  for (var i = 0; i < n; i++) {
    final bits = unsignedView[i];
    // Branchless optimization could be applied here, but explicit branching
    // is often faster due to CPU branch prediction
    unsignedView[i] = (bits & signMask) != 0
        ? ~bits // Negative float: flip all bits
        : bits ^ signMask; // Positive float: flip sign bit only
  }

  // 2. Sort: Call the core 64-bit sorting logic
  radixSortCore64(unsignedView, reuseBuffer: reuseBuffer);

  // 3. Transform back: Revert the transformation
  for (var i = 0; i < n; i++) {
    final bits = unsignedView[i];
    unsignedView[i] = (bits & signMask) != 0
        ? bits ^
              signMask // Originally positive: flip sign bit only
        : ~bits; // Originally negative: flip all bits
  }

  // 4. Copy back if needed (if we created a temporary Float64List)
  if (!isDirectView) {
    for (var i = 0; i < n; i++) {
      data[i] = workingList[i];
    }
  }

  // 5. Handle descending sort efficiently
  if (!ascending) {
    _reverseInPlaceDouble(data);
  }
}