Module sort

Parallel Slice sorting

This implementation is mostly copied from the core::slice::sort module, with minimal changes to support stable Rust and parallel is_less (e.g. Fn rather than FnMut).

---

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

InsertionHole 🔒

MergeHole 🔒

TimSortRun 🔒

Internal type used by merge_sort.

Enums

MergeSortResult 🔒

The result of merge sort.

Functions

break_patterns 🔒

Scatters some elements around in an attempt to break patterns that might cause imbalanced partitions in quicksort.

choose_pivot 🔒

Chooses a pivot in v and returns the index and true if the slice is likely already sorted.

find_streak 🔒

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.

heapsort 🔒

Sorts v using heapsort, which guarantees O(n * log(n)) worst-case.

insert_head 🔒 ^⚠

Inserts v[0] into pre-sorted sequence v[1..] so that whole v[..] becomes sorted.

insert_tail 🔒 ^⚠

Inserts v[v.len() - 1] into pre-sorted sequence v[..v.len() - 1] so that whole v[..] becomes sorted.

insertion_sort_shift_left 🔒

Sort v assuming v[..offset] is already sorted.

insertion_sort_shift_right 🔒

Sort v assuming v[offset..] is already sorted.

merge 🔒 ^⚠

Merges non-decreasing runs v[..mid] and v[mid..] using buf as temporary storage, and stores the result into v[..].

merge_recurse 🔒 ^⚠

Recursively merges pre-sorted chunks inside v.

merge_sort 🔒 ^⚠

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.

par_merge 🔒 ^⚠

Merges slices left and right in parallel and stores the result into dest.

par_mergesort 🔒

Sorts v using merge sort in parallel.

par_quicksort 🔒

Sorts v using pattern-defeating quicksort in parallel.

partial_insertion_sort 🔒

Partially sorts a slice by shifting several out-of-order elements around.

partition 🔒

Partitions v into elements smaller than v[pivot], followed by elements greater than or equal to v[pivot].

partition_equal 🔒

Partitions v into elements equal to v[pivot] followed by elements greater than v[pivot].

partition_in_blocks 🔒

Partitions v into elements smaller than pivot, followed by elements greater than or equal to pivot.

provide_sorted_batch 🔒

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.

recurse 🔒

Sorts v recursively.

split_for_merge 🔒

Splits two sorted slices so that they can be merged in parallel.