smallsort - core

Structs

CopyMarker SAFETY: Only used for run-time optimization heuristic.
StableSmallSortTypeImpl Using a trait allows us to specialize on Freeze which in turn allows us to make safe abstractions.
UnstableSmallSortFreezeTypeImpl FIXME(const_trait_impl) use original ipnsort approach with choose_unstable_small_sort, as found here https://github.com/Voultapher/sort-research-rs/blob/438fad5d0495f65d4b72aa87f0b62fc96611dff3/ipnsort/src/smallsort.rs#L83C10-L83C36.
UnstableSmallSortTypeImpl Using a trait allows us to specialize on Freeze which in turn allows us to make safe abstractions.

bidirectional_merge Merge v assuming v[..len / 2] and v[len / 2..] are sorted.
has_efficient_in_place_swap
insert_tail Sorts range [begin, tail] assuming [begin, tail) is already sorted.
insertion_sort_shift_left Sort v assuming v[..offset] is already sorted.
merge_down
merge_up
panic_on_ord_violation
small_sort_fallback
small_sort_general
small_sort_general_with_scratch
small_sort_network
sort13_optimal Sorts the first 13 elements of v with a fast fixed function.
sort4_stable SAFETY: The caller MUST guarantee that v_base is valid for 4 reads and dst is valid for 4 writes. The result will be stored in dst[0..4].
sort8_stable SAFETY: The caller MUST guarantee that v_base is valid for 8 reads and writes, scratch_base and dst MUST be valid for 8 writes. The result will be stored in dst[0..8].
sort9_optimal Sorts the first 9 elements of v with a fast fixed function.
swap_if_less Swap two values in the slice pointed to by v_base at the position a_pos and b_pos if the value at position b_pos is less than the one at position a_pos.

MAX_STACK_ARRAY_SIZE Using a stack array, could cause a stack overflow if the type T is very large. To be conservative we limit the usage of small-sorts that require a stack array to types that fit within this limit.
SMALL_SORT_FALLBACK_THRESHOLD Optimal number of comparisons, and good perf.
SMALL_SORT_GENERAL_SCRATCH_LEN small_sort_general uses sort8_stable as primitive and does a kind of ping-pong merge, where the output of the first two sort8_stable calls is stored at the end of the scratch buffer. This simplifies panic handling and avoids additional copies. This affects the required scratch buffer size.
SMALL_SORT_GENERAL_THRESHOLD From a comparison perspective 20 was ~2% more efficient for fully random input, but for wall-clock performance choosing 32 yielded better performance overall.
SMALL_SORT_NETWORK_SCRATCH_LEN
SMALL_SORT_NETWORK_THRESHOLD SAFETY: If you change this value, you have to adjust small_sort_network !