Module core::slice::sort

source ·
🔬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.