plf_indiesort

A sort wrapper enabling use of random-access (eg. std::sort) sorting on non-random access containers, and increased performance for the sorting of large types in random-access containers.

It has a temporary memory cost of N * (sizeof(pointer) + sizeof(size_t)) for sorting non-random-access iterators/containers,
and a N * sizeof(U) cost for random-access iterators/containers, where U = the smallest unsigned integer able to store N. For example if the size of the range being sorted is <= 255, U will be unsigned char.

Indiesort should be used when:

• The temporary memory cost mentioned is non-problematic,
• The container or iterators are not random_access and therefore std::sort cannot be used, and/or
• The element type is large or non-trivially-movable/copyable.

It is, on average across all numbers of sorted elements:

• +146% faster than std::sort when used on vectors or arrays of large structs (496 bytes). Crossover point for increased performance over std::sort is any type larger than 152 bytes.
• +28% faster than std::list's internal sort, on types smaller than 272 bytes.

std::list's internal sort is faster for types larger than 272 bytes (as it only writes previous and next pointers) and std::sort is faster on vectors and arrays for types smaller than 152 bytes. C++98/03/11/14/etc-compatible.