Module parallel_sort 

Parallel sorting and reduction utilities (CPU-side, rayon-based).

Provides:

• radix_sort_u32 – LSD radix sort for u32 (4 passes of 8 bits).
• radix_sort_by_key – sort any T by a u32 key function.
• parallel_prefix_sum – exclusive prefix-sum (scan) via rayon.
• parallel_reduce_sum – parallel tree reduction for f64.
• parallel_min_max – parallel min/max reduction.
• bitonic_sort – bitonic sort (pads to power-of-2 with f64::MAX).
• merge_sort_parallel – parallel merge sort via rayon.
• histogram_u32 – parallel histogram.
• argsort – sorted index array for f64 slice.
• nth_element – quickselect O(n) kth smallest element.

Structs

SortTimingResult

Sort timing result for performance comparison.

SortValidation

Comprehensive sort validation: check sorted + permutation + stable order.

Functions

adaptive_bucket_sort

Frequency-adaptive bucket sort: allocates buckets proportional to data density.

argsort

Return indices that would sort data in ascending order.

bitonic_sort

Bitonic sort of a Vecf64` in ascending order.

compare_sorts

Run all three sort algorithms on a copy of the data and verify correctness.

count_inversions_f64

Count the number of inversions (pairs where data[i] > data[j] for i < j).

counting_sort_by_key

Counting sort that also carries satellite data (key-value pairs).

counting_sort_u32

Integer counting sort for values in [0, max_val].

histogram_bucket_sort

Bucket sort for f64 values using a histogram to distribute elements.

histogram_u32

Parallel histogram: count occurrences of data[i] % num_buckets per bucket.

is_permutation_f64

Check if two slices contain the same elements (as a multiset).

is_permutation_u32

Check if two u32 slices contain the same elements.

is_sorted_f64

Verify that a slice of f64 is sorted in ascending order.

is_sorted_u32

Verify that a slice of u32 is sorted in ascending order.

k_way_merge

K-way merge of multiple sorted slices using a min-heap approach.

merge_sort_parallel

Parallel merge sort of a Vecf64` using rayon.

merge_sort_parallel_threshold

Parallel merge sort with configurable thread threshold.

merge_sorted

Merge two sorted slices into a single sorted Vec.

merge_sorted_u32

Merge two sorted u32 slices.

nth_element

Quickselect O(n) algorithm: rearranges data so that data\[k\] holds the value that would be there in a fully sorted array, and returns it.

parallel_min_max

Parallel min/max reduction over a f64 slice.

parallel_prefix_sum

Exclusive prefix sum (scan) of data using rayon work-stealing.

parallel_reduce_sum

Parallel tree reduction: sum all f64 values in data.

radix_histogram

Stage histogram: compute per-bucket histogram for a given bit range.

radix_sort_by_key

Sort a VecTin ascending order of theu32key produced bykey_fn`.

radix_sort_gpu_staged

Full 4-pass GPU radix sort decomposed into individual stages.

radix_sort_stage_u32

GPU-style radix sort stage: one pass sorting by 8 bits starting at shift.

radix_sort_u32

LSD radix sort for u32 values using 8-bit passes (4 passes total).

validate_radix_sort

Validate that radix sort preserves all elements as a multiset.