IntroSort

Available on macOS, Linux, Windows, Wasm

#import "IntroSort";

The comparator sorts that Sort is built from, for callers that want a specific algorithm: intro_sort for general use, insertion_sort for short or nearly sorted arrays.

Example↗

values := int.[5, 2, 9, 1];
intro_sort(values, (a: int, b: int) -> int { return a - b; });
assert(values[0] == 1 && values[3] == 9);

Procedures#

intro_sortSource

(array: [] $T, f: (T, T) -> $R)

Sorts an array view in place with a three-way comparator: negative, zero or positive. Quicksort partitions around a median of three; a range that nests too deep falls back to heap_sort, and short ranges finish with insertion_sort.

insertion_sortSource

(array: [] $T, f: (T, T) -> $R)

Sorts an array view in place by insertion with a three-way comparator.