Function voracious_radix_sort::thiel_radixsort

source ·

pub fn thiel_radixsort<T, K>(arr: &mut [T], radix: usize)where
    T: Radixable<K>,
    K: RadixKey,

Expand description

Thiel sort

An implementation of the Fast radix sort algorithm. (Same author as the DFR sort)

We haven’t managed to reproduce the Fast radix sort performance. Maybe the generic implementation prevent us from reaching the same runtimes as the original algorithm which has a dedicated implementation for integers.

The Verge sort pre-processing heuristic is also added.

The Thiel sort is an out of place unstable radix sort. The original sort is stable, but because the fallback has been replaced by an unstable sort, the entire algorithm is then unstable.

Since this sort is not used in this crate, it is not fully optimized and implemented. It won’t work for u128 and i128.