Module core::slice::sort

🔬This is a nightly-only experimental API. (slice_internals)

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

• InsertionHole 🔒 Experimental
• TimSortRunExperimental
  Internal type used by merge_sort.

Functions

• break_patterns 🔒 Experimental
  Scatters some elements around in an attempt to break patterns that might cause imbalanced partitions in quicksort.
• choose_pivot 🔒 Experimental
  Chooses a pivot in v and returns the index and true if the slice is likely already sorted.
• find_streak 🔒 Experimental
  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.
• heapsortExperimental
  Sorts v using heapsort, which guarantees O(n * log(n)) worst-case.
• insert_head 🔒 ^⚠Experimental
  Inserts v[0] into pre-sorted sequence v[1..] so that whole v[..] becomes sorted.
• insert_tail 🔒 ^⚠Experimental
  Inserts v[v.len() - 1] into pre-sorted sequence v[..v.len() - 1] so that whole v[..] becomes sorted.
• insertion_sort_shift_left 🔒 Experimental
  Sort v assuming v[..offset] is already sorted.
• insertion_sort_shift_right 🔒 Experimental
  Sort v assuming v[offset..] is already sorted.
• merge 🔒 ^⚠Experimental
  Merges non-decreasing runs v[..mid] and v[mid..] using buf as temporary storage, and stores the result into v[..].
• 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.
• partial_insertion_sort 🔒 Experimental
  Partially sorts a slice by shifting several out-of-order elements around.
• partition 🔒 Experimental
  Partitions v into elements smaller than v[pivot], followed by elements greater than or equal to v[pivot].
• partition_equal 🔒 Experimental
  Partitions v into elements equal to v[pivot] followed by elements greater than v[pivot].
• partition_in_blocks 🔒 Experimental
  Partitions v into elements smaller than pivot, followed by elements greater than or equal to pivot.
• provide_sorted_batch 🔒 Experimental
  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.
• quicksortExperimental
  Sorts v using pattern-defeating quicksort, which is O(n * log(n)) worst-case.
• recurse 🔒 Experimental
  Sorts v recursively.