Repository files navigation

It would be nice if only one or two of the sorting methods would dominate all of the others,regardless of application or the computer being used. But in fact, each method has its ownpeculiar virtues. [...] Thus we find that nearly all of the algorithms deserve to be remembered,since there are some applications in which they turn out to be best.— Donald Knuth, The Art Of Computer Programming, Volume 3

cpp-sort is a generic C++17 header-only sorting library. It revolvesaround one main generic sorting interface and provides several small toolsto pick and/or design sorting algorithms. Using its basic sorting featuresshould be trivial enough:

#include<array>#include<iostream>#include<cpp-sort/sorters/smooth_sorter.h>intmain(){    std::array<int,5> arr = {5,8,3,2,9 };cppsort::smooth_sort(arr);// prints 2 3 5 8 9for (int val: arr) {        std::cout << val <<'';    }}

Note: older versions of the library targeting C++14 are still available in the1.x.y-developand1.x.y-stable, but they are not actively developed anymore. Open an issue if you needanything to be backported.

cpp-sort provides a full set of sorting-related features. Here are the main building blocksof the library:

• Every sorting algorithm exists as a function object called asorter
• Sorters can be wrapped insorter adapters to augment their behaviour
• The library provides asorter facade to easily build sorters
• Fixed-size sorters can be used to efficiently sort tiny fixed-size collections
• Measures of disorder can be used to evaluate the disorder in a collection

Here is a more complete example of what can be done with the library:

#include<algorithm>#include<cassert>#include<forward_list>#include<functional>#include<vector>#include<cpp-sort/adapters.h>#include<cpp-sort/sorters.h>intmain(){structwrapper {int value; };    std::forward_list<wrapper> li = { {5}, {8}, {3}, {2}, {9} };    std::vector<wrapper> vec = { {5}, {8}, {3}, {2}, {9} };// When used, this sorter will use a pattern-defeating quicksort// to sort random-access collections, and a mergesort otherwise    cppsort::hybrid_adapter<        cppsort::pdq_sorter,        cppsort::merge_sorter    > sorter;// Sort li and vec in reverse order using their value membersorter(li, std::greater{}, &wrapper::value);sorter(vec, std::greater{}, &wrapper::value);assert(std::equal(        li.begin(), li.end(),        vec.begin(), vec.end(),        [](constauto& lhs,constauto& rhs) {return lhs.value == rhs.value; }    ));}

Even when the sorting functions are used without the extra features, they still providesome interesting guarantees (ideas often taken from the Ranges TS):

• They provide both an iterator and a range interface
• When possible, they accept a custom comparator parameter
• Most of them accept a projection parameter
• They correctly handle proxy iterators withiter_swap anditer_move
• They also work when iterators don't provide post-incrementation nor post-decrementation
• The value types of the collections to be sorted need not be default-constructible
• The value types of the collections to be sorted need not be copyable (only movable)
• Stateless sorters can be converted to a function pointer for each overloadedoperator()
• Sorters are function objects: they can directly be passed as "overload sets" to other functions

You can read more about all the available tools and find some tutorials about usingand extendingcpp-sort inthe wiki.

The following graph has been generated with a script found in the benchmarksdirectory. It shows the time needed forheap_sort to sort onemillion elements without being adapted, then when it is adapted with eitherdrop_merge_adapter orsplit_adapter.

As can be seen above, wrappingheap_sort with either of the adapters makes itadaptive to the number of inversions in a non-intrusivemanner. The algorithms used to adapt it have different pros and cons, it is upto you to use either.

This benchmark is mostly there to show the possibilities offered by thelibrary. You can find more such commented benchmarks in thededicated wikipage.

cpp-sort requires C++17 support, and should work with the following compilers:

• g++-9 or more recent.
• clang++-11 or more recent (with both libstdc++ and libc++).
• The versions of MinGW-w64 and AppleClang equivalent to the compilers mentioned above.
• Visual Studio 2022 version 17.14.36414.22 or more recent, only with/permissive-. A few features are unavailable.
• clang-cl corresponding the the Visual Studio version above.

The compilers listed above are the ones used by the CI pipeline, and the library is also testedwith the most recent versions of those compilers on a regular basis. All the other compilerversions in-between are untested, but should also work. Feel free to open an issue if it isn't thecase.

The features in the library might differ depending on the C++ version used and on the compilerextensions enabled. Those changes are documentedin the wiki.

The main repository contains additional support for standard tooling such as CMake or Conan.You can read more about thosein the wiki.

I got a new car. I just need to put it together. They’re easier to steal piece bypiece.— Jarod Kintz, $3.33

Even though some parts of the library areoriginal researchand some others correspond to custom and rather naive implementations of standardsorting algorithms,cpp-sort also reuses a great deal of code and ideas fromopen-source projects, often altered to integrate seamlessly into the library. Hereis a list of the external resources used to create this library. I hope that themany different licenses are compatible. If it is not the case, please contact me(or submit an issue) and we will see what can be done about it:

• Some of the algorithms used byinsertion_sorter andpdq_sorter come fromOrson Peters'pattern-defeating quicksort. Someparts of the benchmarks come from there as well.

• The algorithm used bytim_sorter comes from Goro Fuji's (gfx)implementationof a Timsort.

• The three algorithms used byspread_sorter come from Steven RossBoost.Sortmodule.

• The algorithm used byd_ary_spread_sorter comes from Tim Blechmann'sBoost.Heap module.

• The algorithm used byspin_sorter comes from the eponymous algorithm implementedinBoost.Sort.by Francisco Jose Tapia.

• utility::as_function,and several projection-enhanced helper algorithms come from Eric Niebler'sRangev3 library. Several ideas such as proxyiterators, customization points and projections, as well as a few other utilityfunctions also come from that library or from the related articles and standardC++ proposals.

• The algorithm used byska_sorter comes from Malte Skarupke'simplementationof his ownska_sort algorithm.

• The algorithm used bydrop_merge_adapter comes from Adrian WielgosikC++reimplementation of Emil Ernerfeldt'sdrop-merge sort.

• Many enhanced standard algorithms are directly adapted from their counterpartsinlibc++, enhanced to handle both projections andproxy iterators.

• The library internally uses aninplace_merge function that works with forwarditerators. Its implementation uses a merge algorithm proposed by Dudziński and Dydek,and implemented by Alexander Stepanov and Paul McJones in their bookElements ofProgramming.

• Theinplace_merge overload for random-access iterators uses theSymmerge algorithmproposed by Pok-Son Kim and Arne Kutzner inStable Minimum Storage Merging by SymmetricComparisonswhen there isn't enough memory available to perform an out-of-place merge.

• The implementation of Dijkstra's smoothsort used bysmooth_sorter has beendirectly adapted fromKeith Schwarz's implementationof the algorithm.

• The algorithm used bywiki_sorter has been adapted from BonzaiThePenguin'sWikiSort.

• The algorithm used bygrail_sorter has been adapted from Mrrl'sGrailSort.

• The algorithm used byindirect_adapter with forward or bidirectional iterators is aslightly modified version of Matthew Bentley'sindiesort.

• The implementation of the random-access overload ofnth_element used by some of the algorithmscomes from Danila Kutenin'sminiselect library and usesAndrei Alexandrescu'sAdaptiveQuickselect algorithm.

• The sorting networks used bysorting_network_sorter all comefrom this listmaintained by Bert Dobbelaere. The page has references to the sources of all of the sorting networksit lists.

• Some of the optimizations used bysorting_network_sorter come fromthisdiscussion on StackOverflow and arebacked by the articleApplying Sorting Networks to Synthesize Optimized SortingLibraries.

• The algorithm behindutility::quicksort_adversary is a fairly straightforward adaptation of theone provided by M. D. McIlroy inA Killer Adversary for Quicksort.

• The test suite reimplements random number algorithms originally found in the following places:

  • xoshiro256**
  • Optimal Discrete Uniform Generation from Coin Flips, and Applications
  • All numbers in a given range but random order

• The LaTeX scripts used to draw the sorting networks are modified versions ofkaayy'ssortingnetwork.tex,slightly adapted to be 0-based and draw the network from top to bottom.

• The CMake tools embedded in the projects include scripts fromRWTH-HPC/CMake-codecov.

• Some of the benchmarks use acolorblind-friendly palettedeveloped by Thøger Rivera-Thorsen.