folly::stable_radix_sort_detail::insertionSort

Stable insertion sort for small inputs. O(n^2) but fast for small n due to low overhead.

Synopsis

Declared in <folly/algorithm/StableRadixSort.h>

template<
    typename RandomIt,
    typename Projection>
void
insertionSort(
    RandomIt first,
    RandomIt last,
    Projection proj);

Parameters

NameDescription
firstIterator to the first element to sort.
lastIterator past the last element to sort.
projProjection returning the sort key for each element.