Module quicksort

Parallel quicksort.

This implementation is copied verbatim from std::slice::sort_unstable and then parallelized. The only difference from the original is that calls to recurse are executed in parallel using rayon_core::join.

Structs

• CopyOnDrop 🔒
  When dropped, copies from src into dest.

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.
• heapsort 🔒
  Sorts v using heapsort, which guarantees O(n * log(n)) worst-case.
• insertion_sort 🔒
  Sorts a slice using insertion sort, which is O(n^2) worst-case.
• 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.
• recurse 🔒
  Sorts v recursively.
• shift_head 🔒
  Shifts the first element to the right until it encounters a greater or equal element.
• shift_tail 🔒
  Shifts the last element to the left until it encounters a smaller or equal element.