Module mergesort

Parallel merge sort.

This implementation is copied verbatim from std::slice::sort and then parallelized. The only difference from the original is that the sequential mergesort returns MergesortResult and leaves descending arrays intact.

Structs

• CopyOnDrop 🔒
  When dropped, copies from src into dest a sequence of length len.
• Run 🔒
  A sorted run that starts at index start and is of length len.

Enums

• MergesortResult 🔒
  The result of merge sort.

Functions

• collapse 🔒
  Examines the stack of runs and identifies the next pair of runs to merge. More specifically, if Some(r) is returned, that means runs[r] and runs[r + 1] must be merged next. If the algorithm should continue building a new run instead, None is returned.
• decrement_and_get 🔒 ^⚠
• get_and_increment 🔒 ^⚠
• insert_head 🔒
  Inserts v[0] into pre-sorted sequence v[1..] so that whole v[..] becomes sorted.
• merge 🔒 ^⚠
  Merges non-decreasing runs v[..mid] and v[mid..] using buf as temporary storage, and stores the result into v[..].
• mergesort 🔒 ^⚠
  Sorts a slice using merge sort, unless it is already in descending order.
• par_merge 🔒 ^⚠
  Merges slices left and right in parallel and stores the result into dest.
• par_mergesort 🔒
  Sorts v using merge sort in parallel.
• recurse 🔒 ^⚠
  Recursively merges pre-sorted chunks inside v.
• split_for_merge 🔒
  Splits two sorted slices so that they can be merged in parallel.