folly::stable_radix_sort_keys

Description

A stable, O(n) radix sort implementation using counting sort with alternating buffers. Unlike MSD radix sort (e.g., boost::spreadsort), LSD radix sort processes digits from least to most significant, which inherently preserves stability.

Key features:

• Stable: elements with equal keys preserve their original relative order

• O(n) time complexity: k passes of O(n + 256) where k = sizeof(key)/8

• O(n) space complexity: requires a temporary buffer

• Supports ascending and descending order

• Supports custom projections for sorting by member fields

• Handles floating-point keys via IEEE 754 bit transformation

Example usage:

// Sort vector of integers std::vector<uint64_t> values = {5, 2, 8, 1, 9}; folly::stable_radix_sort(values.begin(), values.end());

// Sort by struct member struct Item { double score; int id; }; std::vector<Item> items = ...; folly::stable_radix_sort( items.begin(), items.end(), []Item& item) { return item.score; });

// Sort descending folly::stable_radix_sort_descending(values.begin(), values.end());