-
Notifications
You must be signed in to change notification settings - Fork 58
Sorters
cpp-sort uses function objects called sorters instead of regular function templates in order to implement sorting algorithms. The library provides two categories of sorters: comparison sorters, that sort a collection with using a weak order comparator, and type-specific sorters that use other strategies to sort collections, generally restricting their domain to specific types. Every comparison sorter as well as some type-specific sorters may also take an additional projection parameter, allowing the algorithm to "view" the data to sort through an on-the-fly transformation. (see unified sorting interface)
While these function objects offer little more than regular sorting functions by themselves, they can be used together with sorter adapters to craft more elaborate sorters. Every sorter is available in its own file. However, all the available sorters can be included at once with the following line:
#include <cpp-sort/sorters.h>
For every foobar_sorter
described in this page, there is a corresponding foobar_sort
global instance that allows not to care about the sorter abstraction as long as it is not needed (the instances are usable as regular function templates). The only sorter without a corresponding global instance is default_sorter
since it mainly exists as a fallback sorter for the functions cppsort::sort
and cppsort::stable_sort
when they are called without an explicit sorter.
If you want to read more about sorters and/or write your own one, then you should have a look at the dedicated page or at a specific example.
The following sorters are available and should work with any type for which std::less
works and should accept any weak order comparison function:
#include <cpp-sort/sorters/adaptive_shivers_sorter.h>
Implements an adative ShiversSort, a k-aware natural mergesort with a better worst case than timsort described by Vincent Jugé in Adaptive Shivers Sort: An Alternative Sorting Algorithm.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n log n | n log n | n | Yes | Random-access |
While the sorting algorithm is stable and the complexity guarantees are good enough, this sorter is rather slow compared to the some other ones when the data distribution is random. That said, it would probably be a good choice when comparing data is expensive, but moving it is inexpensive (this is the use case for which it was designed).
New in version 1.13.0
#include <cpp-sort/sorters/block_sorter.h>
WARNING: block_sorter
is deprecated in version 1.11.0 and removed in version 2.0.0, use wiki_sorter
instead.
#include <cpp-sort/sorters/cartesian_tree_sorter.h>
Implements a Cartesian tree sort, a rather slow but highly adaptive algorithm described by C. Levcopoulos and O. Petersson in Heapsort - Adapted for Presorted Files.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n log n | n log n | n | No | Forward |
New in version 1.10.0
Changed in version 1.11.0: cartesian_tree_sorter
now works with forward iterators. It used to only work with random-access iterators.
#include <cpp-sort/sorters/d_ary_heap_sorter.h>
Implements a heapsort algorithm based on a d-ary heap: the value of D is an integer template parameter that can be passed to either d_ary_heap_sort
or d_ary_heap_sorter
. That value cannot be smaller than 2.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n log n | n log n | n log n | 1 | No | Random-access |
d-ary heapsorts are more complicated than their binary counterparts, but storing more elements in each node can improve locality of reference and improve the execution speed. This sorter, unlike heap_sorter
, does not implement a bottom-up node searching strategy.
New in version 1.14.0
#include <cpp-sort/sorters/default_sorter.h>
WARNING: default_sorter
is deprecated in version 1.8.0 and removed in version 2.0.0, see issue #168 for the rationale.
Sorter striving to use a sorting algorithm as optimized as possible. It is the fallback sorter used by cppsort::sort
when no sorter is given. The current implementation defines it as follows:
struct default_sorter:
self_sort_adapter<
hybrid_adapter<
small_array_adapter<
low_comparisons_sorter,
std::make_index_sequence<14u>
>,
quick_sorter,
pdq_sorter
>
>
{};
The adapter stable_adapter
has an explicit specialization for default_sorter
defined as follows:
template<>
struct stable_adapter<default_sorter>:
merge_sorter
{};
Deprecated in version 1.8.0
Removed in version 2.0.0
#include <cpp-sort/sorters/drop_merge_sorter.h>
WARNING: drop_merge_sorter
is deprecated in version 1.15.0 and removed in version 2.0.0, use drop_merge_adapter
(
pdq_sort
)
instead.
Implements a drop-merge sort.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n log n | n log n | n | No | Bidirectional |
Drop-merge sort is a Rem-adaptive sorting algorithm. While it is not as good as other sorting algorithms to sort shuffled data, it is excellent when more than 80% of the data is already ordered according to Rem.
Deprecated in version 1.15.0
Removed in version 2.0.0
#include <cpp-sort/sorters/grail_sorter.h>
Implements a Grail sort.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
? | n log n | n log n | 1 | Yes | Random-access |
grail_sorter
is a buffered sorter whose default specialization achieves O(1) auxiliary memory by not actualy allocating any additional memomry. The memory complexity may change depending of the buffer provider passed to it.
template<
typename BufferProvider = utility::fixed_buffer<0>
>
struct grail_sorter;
Whether this sorter works with types that are not default-constructible depends on the memory allocation strategy of the buffer provider. The default specialization works with such types.
Changed in version 1.5.0: grail_sorter
now handles comparison and projection objects that aren't default-constructible.
#include <cpp-sort/sorters/heap_sorter.h>
Implements a bottom-up heapsort.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n log n | n log n | n log n | 1 | No | Random-access |
#include <cpp-sort/sorters/insertion_sorter.h>
Implements an insertion sort.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n² | n² | 1 | Yes | Bidirectional |
This sorter also has the following dedicated algorithms when used together with container_aware_adapter
:
Container | Best | Average | Worst | Memory | Stable |
---|---|---|---|---|---|
std::list |
n | n² | n² | 1 | Yes |
std::forward_list |
n | n² | n² | 1 | Yes |
None of the container-aware algorithms invalidates iterators.
#include <cpp-sort/sorters/mel_sorter.h>
Implements melsort, a rather slow but Enc-adaptive algorithm described by S. Skiena in Encroaching lists as a measure of presortedness.
MEL stands for Merge Encroaching Lists.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n log n | n log n | n | No | Forward |
This sorter also has the following dedicated algorithms when used together with container_aware_adapter
:
Container | Best | Average | Worst | Memory | Stable |
---|---|---|---|---|---|
std::list |
n | n log n | n log n | n | No |
std::forward_list |
n | n log n | n log n | n | No |
None of the container-aware algorithms invalidates iterators.
New in version 1.10.0
#include <cpp-sort/sorters/merge_insertion_sorter.h>
Implements the Ford-Johnson merge-insertion sort. This algorithm isn't meant to actually be used and is mostly interesting from a computer science point of view: for really small collections, it has an optimal worst case for the number of comparisons performed. It has indeed been proved that for some sizes, no algorithm can perform fewer comparisons. That said, the algorithm has a rather big memory overhead and performs many move operations; it is really too slow for any real world use.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
? | n log n | n log n | n | No | Random-access |
Until version 1.7.0: the algorithm used GNU's bitmap_allocator
with std::list
when possible instead of the default allocator, leading to speed improvements up to 25%.
Changed in version 1.7.0: the std::list
used by the algorithm has been replaced with a custom list implementation whose speed does not depend on the availability of some allocator, and which should be faster than the previous implementation in any case (still not anywhere near fast).
#include <cpp-sort/sorters/merge_sorter.h>
Implements a merge sort.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n log n | n log n | n log n | n | Yes | Forward |
n log n | n log n | n log² n | log n | Yes | Forward |
When additional memory is available, merge_sorter
runs in O(n log n), however if there is no additional memory available, it uses a O(n log² n) algorithm instead. The merging algorithm is memory adaptive, so even if it can only allocate a bit of memory instead of all the memory it needs, it will still take advantage of this additional memory. This memory scheme means that this sorter can't throw std::bad_alloc
.
This sorter also has the following dedicated algorithms when used together with container_aware_adapter
:
Container | Best | Average | Worst | Memory | Stable |
---|---|---|---|---|---|
std::list |
n log n | n log n | n log n | log n | Yes |
std::forward_list |
n log n | n log n | n log n | log n | Yes |
None of the container-aware algorithms invalidates iterators.
#include <cpp-sort/sorters/pdq_sorter.h>
Implements a pattern-defeating quicksort.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n log n | n log n | log n | No | Random-access |
pdq_sorter
uses a more performant partitioning algorithm under the hood if the comparison and projection functions generate branchless code. You can provide this information to the algorithm by specializing the library's branchless traits for the given comparison/type or projection/type pairs if they aren't arleady handled natively by the library.
This sorter can't throw std::bad_alloc
.
#include <cpp-sort/sorters/poplar_sorter.h>
Implements a poplar sort, which is a heapsort derivate described by Coenraad Bron and Wim H. Hesselink in Smoothsort revisited. It builds a forest of perfect max heaps whose roots are stored on the right, then unheaps the elements to sort the collection.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n log n | n log n | n log n | log n | No | Random-access |
This sorter is a bit faster or a bit slower than smooth_sorter
depending on the patterns in the data to sort. I don't think it has any real advantage over heap_sorter
in production code.
#include <cpp-sort/sorters/quick_merge_sorter.h>
Implements a flavour of QuickMergesort.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n log n | n log n | log n | No | Random-access |
n | n log n | n log n | log² n | No | Forward |
QuickMergesort is an algorithm that performs a quicksort-like partition and tries to use mergesort on the bigger partition, using the smaller one as a swap buffer used for the merge operation when possible. The flavour of QuickMergesort used by quick_merge_sorter
uses a selection algorithm to split the collection into partitions containing 2/3 and 1/3 of the elements respectively. This allows to use an internal mergesort of the biggest partition (2/3 of the elements) using the other partition (1/3 of the elements) as a swap buffer.
The space complexity is dominated by the stack recursion in the selection algorithms:
- log n for the random-access version, which uses Andrei Alexandrescu's AdaptiveQuickselect.
- log² n for the forward and bidirectional versions, which use the mutually recursive introselect algorithm.
This sorter can't throw std::bad_alloc
.
New in version 1.2.0
Changed in version 1.9.0: the random-access version now runs in O(n log n) instead of accidentally running in O(n²).
#include <cpp-sort/sorters/quick_sorter.h>
Implements a quicksort.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n log n | n log n | log² n | No | Forward |
Despite the name, this sorter actually implements some flavour of introsort: if quicksort performs more than 2*log(n) steps, it falls back to a median-of-medians pivot selection instead of the usual median-of-9 one. The median-of-medians selection being mutually recursive with an introselect algorithm explains the use of log²n stack memory.
This sorter can't throw std::bad_alloc
.
Changed in version 1.2.0: quick_sorter
used to run in O(n²), but a fallback to median-of-medians pivot selection was introduced to make it run in O(n log n) or O(n log² n) depending of the iterator category, the tradeoff being the log² n space used by stack recursion (as opposed to the previous log n one).
#include <cpp-sort/sorters/selection_sorter.h>
Implements a selection sort.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n² | n² | n² | 1 | No | Forward |
This sorter also has the following dedicated algorithms when used together with container_aware_adapter
:
Container | Best | Average | Worst | Memory | Stable |
---|---|---|---|---|---|
std::list |
n² | n² | n² | 1 | Yes |
std::forward_list |
n² | n² | n² | 1 | Yes |
None of the container-aware algorithms invalidates iterators.
#include <cpp-sort/sorters/slab_sorter.h>
Implements a variant of slabsort, a rather slow but highly adaptive algorithm described by C. Levcopoulos and O. Petersson in Sorting Shuffled Monotone Sequences.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n log n | n log n | n | No | Bidirectional |
This algorithm actually uses a rather big amount of memory but scales better than other O(n log n) algorithms of the library described as "slow" when the collections get bigger.
New in version 1.10.0
Changed in version 1.12.1: slab_sorter
now works with bidirectional iterators.
#include <cpp-sort/sorters/smooth_sorter.h>
Implements a smoothsort.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n log n | n log n | 1 | No | Random-access |
While the complexity guarantees of this algorithm are optimal, this smoothsort isn't actually fast in practice. Except for some specific patterns (where tim_sorter
or pdq_sorter
are still faster anyway), it is always almost twice as slow as heap_sorter
. Huge collections and/or huge objects may make a difference, but I have yet to see a case where this is a useful sorting algorithm.
#include <cpp-sort/sorters/spin_sorter.h>
Implements a spinsort.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n log n | n log n | n | Yes | Random-access |
New in version 1.6.0
#include <cpp-sort/sorters/splay_sorter.h>
Implements a splaysort.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n log n | n log n | n | Yes | Forward |
New in version 1.15.0
#include <cpp-sort/sorters/split_sorter.h>
WARNING: split_sorter
is deprecated in version 1.15.0 and removed in version 2.0.0, use split_adapter
(
pdq_sort
)
instead.
Implements an in-place SplitSort as descirbed in Splitsort — an adaptive sorting algorithm by C. Levcopoulos and O. Petersson. This library implements the simpler "in-place" version of the algorithm described in the paper.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n log n | n log n | n | No | Random-access |
SplitSort is a Rem-adaptive sorting algorithm and shares many similarities with drop-merge sort but has the following differences:
- It only works with random-access iterators.
- While it uses O(n) extra memory to merge some elements, it can run perfectly fine with O(1) extra memory.
- Benchmarks shows that drop-merge sort is better when few elements aren't in place, but SplitSort has a lower overhead on random data while still performing better than most general-purpose sorting algorithms when the data is already somewhat sorted.
This sorter can't throw std::bad_alloc
.
New in version 1.4.0
Deprecated in version 1.15.0
Removed in version 2.0.0
#include <cpp-sort/sorters/std_sorter.h>
Uses the standard library std::sort
to sort a collection. While the complexity guarantees are only partial in the standard, here is what's expected:
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n log n | n² * | log n | No | Random-access |
* std::sort
is mandated by the standard to be O(n log n), but the libc++ implementation of the algorithm - despite non-trivial optimizations - is still O(n²). If you are using another standard library implementation then std_sorter
should be O(n log n) for randon-access iterators, as expected.
The adapter stable_adapter
has an explicit specialization for std_sorter
which calls std::stable_sort
instead. Its complexity depends on whether it can allocate additional memory or not. While the complexity guarantees are only partial in the standard, here is what's expected:
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n log n | n log n | n log n | n | Yes | Random-access |
n log² n | n log² n | n log² n | 1 | Yes | Random-access |
std::sort
and std::stable_sort
are likely not able to handle proxy iterators, therefore trying to use std_sorter
with code that relies on proxy iterators (e.g. schwartz_adapter
) is deemed to cause errors. However, some standard libraries provide overloads of standard algorithms for some containers; for example, libc++ has an overload of std::sort
for bit iterators, which means that std_sorter
could be the best choice to sort an std::vector<bool>
.
This sorter can't throw std::bad_alloc
.
#include <cpp-sort/sorters/tim_sorter.h>
Implements a timsort.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n log n | n log n | n | Yes | Random-access |
While the sorting algorithm is stable and the complexity guarantees are good enough, this sorter is rather slow compared to the some other ones when the data distribution is random. That said, it would probably be a good choice when comparing data is expensive, but moving it is inexpensive (this is the use case for which it was designed).
Changed in version 1.5.0: tim_sorter
now handles comparison and projection objects that aren't default-constructible.
#include <cpp-sort/sorters/verge_sorter.h>
Implements a vergesort algorithm backed by a quicksort derivative.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n log n | n log n log log n | n | No | Random-access |
n | n log n | n log n | log n | No | Random-access |
n | n log n | n log n log log n | n | No | Bidirectional |
n | n log n | n log n | log² n | No | Bidirectional |
Vergesort is a Runs-adaptive algorithm (including descending runs) as long as the size of those runs is greater than n / log n; when the runs are smaller, it falls back to another sorting algorithm to sort them (pdqsort for random-access iterators, QuickMergesort otherwise).
Vergesort's complexity is bound either by its optimization layer or by the fallback sorter's complexity:
- When it doesn't find big runs, the complexity is bound by the fallback sorter: depending on the category of iterators you can refer to the tables of either
pdq_sorter
orquick_merge_sorter
. - When it does find big runs, vergesort's complexity is bound by the merging phase of its optimization layer. In such a case,
inplace_merge
is used to merge the runs: it will use additional memory if any is available, in which case vergesort is O(n log n). If there isn't much extra memory available, it may still require O(log n) extra memory (and thus raise anstd::bad_alloc
if there isn't that much memory available) in which case the complexity falls to O(n log n log log n). It should not happen that much, and the additional log log n factor is likely irrelevant for most real-world applications.
When wrapped into stable_adapter
, it has a slightly different behaviour: it detects strictly descending runs instead of non-ascending ones, and wraps the fallback sorter with stable_t
. This make the specialization stable, and faster than just using make_stable
.
Changed in version 1.6.0: when sorting a collection made of bidirectional iterators, verge_sorter
falls back to quick_merge_sorter
instead of quick_sorter
.
New in version 1.9.0: explicit specialization for stable_adapter<verge_sorter>
.
#include <cpp-sort/sorters/wiki_sorter.h>
Implements WikiSort, a kind of block sort.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n log n | n log n | 1 | Yes | Random-access |
wiki_sorter
is a buffered sorter whose default specialization allocates a fixed buffer of 512 elements to achieve O(1) auxiliary memory. This memory complexity may change depending of the buffer provider passed to it.
template<
typename BufferProvider = utility::fixed_buffer<512>
>
struct wiki_sorter;
Whether this sorter works with types that are not default-constructible depends on the memory allocation strategy of the buffer provider. The default specialization does not work with such types.
New in version 1.11.0
The following sorters are available but will only work for some specific types instead of using a user-provided comparison function. Some of them also accept projections as long as the result of the projection can be handled by the sorter.
#include <cpp-sort/sorters/counting_sorter.h>
counting_sorter
implements a simple counting sort. This sorter also supports reverse sorting with std::greater<>
or std::ranges::greater
.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n+r | n+r | n+r | No* | Forward |
This sorter works with any type satisfying the trait std::is_integral
(as well as [un]signed __int128
even when the standard library isn't properly instrumented to handle them). It can be insanely faster than other sorting algorithms when there are only a few different values in a tight range (e.g. values between 0 and 100 in an array of 10000 elements), but will be far too slow and eat too much memory if the range is wider than the number of elements (e.g. an array with two elements whose values are 0 and 100000). No memory is used if the collection is already sorted.
* Since the original integers are discarded and overwritten, whether the algorithm is stable or not does not mean much. Moreover, it can only sort integers, so the potential stability problems shouldn't even be observable.
Changed in version 1.6.0: support for [un]signed __int128
.
Changed in version 1.9.0: conditional support for std::ranges::greater
.
#include <cpp-sort/sorters/ska_sorter.h>
ska_sorter
implements a ska_sort.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n | n log n | ? | No | Random-access |
Even though it isn't based on comparison, ska_sorter
can sort a variety of types in ascending order:
- Any type satisfying the trait
std::is_integral
. -
signed __int128
andunsigned __int128
when available, even when they don't satisfystd::is_integral
. -
float
anddouble
if they satisfy the traitstd::numeric_limits::is_iec559
, and if their sizes are respectively the same as those ofstd::uint32_t
andstd::uin64_t
. - Any
std::pair
orstd::tuple
provided the return type ofstd::get<>
is also handled byska_sort
. - Any type implementing
operator[]
provided its return type is also handled byska_sort
(this includes standard strings and random-access collections).
This sorter accepts projections, as long as ska_sorter
can handle the return type of the projection.
Changed in version 1.2.0: support for [un]signed __int128
.
#include <cpp-sort/sorters/spread_sorter.h>
#include <cpp-sort/sorters/spread_sorter/integer_spread_sorter.h>
#include <cpp-sort/sorters/spread_sorter/float_spread_sorter.h>
#include <cpp-sort/sorters/spread_sorter/string_spread_sorter.h>
spread_sorter
implements a spreadsort.
Best | Average | Worst | Memory | Stable | Iterators |
---|---|---|---|---|---|
n | n √log n | min(n log n, n*k) | k | No | Random-access |
Note: k
represents the key length in bits in the in table above.
It comes into three main flavours (available individually if needed):
-
integer_spread_sorter
works with any type satisfying the traitstd::is_integral
. -
float_spread_sorter
works with any type satisfying the traitstd::numeric_limits::is_iec559
whose size is the same asstd::uint32_t
orstd::uin64_t
. -
string_spread_sorter
works withstd::string
andstd::wstring
(ifwchar_t
is 2 bytes). This sorter also supports reverse sorting withstd::greater<>
andstd::ranges::greater
. In C++17 it also works withstd::string_view
andstd::wstring_view
(ifwchar_t
is 2 bytes).
These sorters accept projections as long as their simplest form can handle the result of the projection. The three of them are aggregated into one main sorter the following way:
struct spread_sorter:
hybrid_adapter<
integer_spread_sorter,
float_spread_sorter,
string_spread_sorter
>
{};
Changed in version 1.9.0: conditional support for std::ranges::greater
.
- Home
- Quickstart
- Sorting library
- Comparators and projections
- Miscellaneous utilities
- Tutorials
- Tooling
- Benchmarks
- Changelog
- Original research