Function rayon::slice::mergesort::mergesort

unsafe fn mergesort<T, F>(
    v: &mut [T],
    buf: *mut T,
    is_less: &F,
) -> MergesortResult
where
    T: Send,
    F: Fn(&T, &T) -> bool + Sync,

Sorts a slice using merge sort, unless it is already in descending order.

This function doesn’t modify the slice if it is already non-descending or descending. Otherwise, it sorts the slice into non-descending order.

This merge sort borrows some (but not all) ideas from TimSort, which is described in detail here.

The algorithm identifies strictly descending and non-descending subsequences, which are called natural runs. There is a stack of pending runs yet to be merged. Each newly found run is pushed onto the stack, and then some pairs of adjacent runs are merged until these two invariants are satisfied:

1. for every i in 1..runs.len(): runs[i - 1].len > runs[i].len
2. for every i in 2..runs.len(): runs[i - 2].len > runs[i - 1].len + runs[i].len

The invariants ensure that the total running time is O(n * log(n)) worst-case.

Safety

The argument buf is used as a temporary buffer and must be at least as long as v.