🔬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
- TimSortRunExperimentalInternal type used by merge_sort.
Functions
- Scatters some elements around in an attempt to break patterns that might cause imbalanced partitions in quicksort.
- Chooses a pivot in
v
and returns the index andtrue
if the slice is likely already sorted. - Finds a streak of presorted elements starting at the beginning of the slice. Returns the first value that is not part of said streak, and a bool denoting whether the streak was reversed. Streaks can be increasing or decreasing.
- heapsortExperimentalSorts
v
using heapsort, which guarantees O(n * log(n)) worst-case. - Inserts
v[0]
into pre-sorted sequencev[1..]
so that wholev[..]
becomes sorted. - Inserts
v[v.len() - 1]
into pre-sorted sequencev[..v.len() - 1]
so that wholev[..]
becomes sorted. - Sort
v
assumingv[..offset]
is already sorted. - Sort
v
assumingv[offset..]
is already sorted. - Merges non-decreasing runs
v[..mid]
andv[mid..]
usingbuf
as temporary storage, and stores the result intov[..]
. - merge_sortExperimentalThis 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.
- Partially sorts a slice by shifting several out-of-order elements around.
- Partitions
v
into elements smaller thanv[pivot]
, followed by elements greater than or equal tov[pivot]
. - Partitions
v
into elements equal tov[pivot]
followed by elements greater thanv[pivot]
. - Partitions
v
into elements smaller thanpivot
, followed by elements greater than or equal topivot
. - Takes a range as denoted by start and end, that is already sorted and extends it to the right if necessary with sorts optimized for smaller ranges such as insertion sort.
- quicksortExperimentalSorts
v
using pattern-defeating quicksort, which is O(n * log(n)) worst-case. - Sorts
v
recursively.