🔬This is a nightly-only experimental API. (
slice_internals
)Expand description
Slice sorting
This module contains a sorting algorithm based on Orson Peters’ pattern-defeating quicksort, published at: https://github.com/orlp/pdqsort
Unstable sorting is compatible with core because it doesn’t allocate memory, unlike our stable sorting implementation.
In addition it also contains the core logic of the stable sort used by slice::sort
based on
TimSort.
Structs
TimSortRunExperimental
Internal type used by merge_sort.
Functions
heapsortExperimental
Sorts
v
using heapsort, which guarantees O(n * log(n)) worst-case.merge_sortExperimental
This merge sort borrows some (but not all) ideas from TimSort, which used to be described in
detail here. However Python
has switched to a Powersort based implementation.
partition_at_indexExperimental
Reorder the slice such that the element at
index
is at its final sorted position.quicksortExperimental
Sorts
v
using pattern-defeating quicksort, which is O(n * log(n)) worst-case.