Sorting algorithms & related tools for C++14


Latest Release Conan Package Code Coverage

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 own peculiar 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++14 header-only sorting library. It revolves around one main generic sorting interface and provides several small tools to pick and/or design sorting algorithms. Using its basic sorting features should be trivial enough:

#include <array>
#include <iostream>
#include <cpp-sort/sorters/smooth_sorter.h>

int main()
    std::array<int, 5> arr = { 5, 8, 3, 2, 9 };

    // prints 2 3 5 8 9
    for (int val: arr) {
        std::cout << val << ' ';

The main features & the extra features

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

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>

int main()
    struct wrapper { 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
    > sorter;

    // Sort li and vec in reverse order using their value member
    sorter(li, std::greater<>{}, &wrapper::value);
    sorter(vec, std::greater<>{}, &wrapper::value);

        li.begin(), li.end(),
        vec.begin(), vec.end(),
        [](const auto& lhs, const auto& rhs) { return lhs.value == rhs.value; }

Even when the sorting functions are used without the extra features, they still provide some 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 with iter_swap and iter_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 overloaded operator()
  • 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 using and extending cpp-sort in the wiki.


The following graph has been generated with a script found in the benchmarks directory. It shows the time needed for a sorting algorithm to sort one million shuffled std::array<int, N> of sizes 0 to 32. It compares the sorters generally used to sort small arrays:

Benchmark speed of small sorts with increasing size for std::array<int>

These results were generated with MinGW-w64 g++ 10.1 with the compiler options -std=c++2a -O3 -march=native. That benchmark is merely an example to make this introduction look good. You can find more commented benchmarks in the dedicated wiki page.

Compiler support & tooling

Ubuntu builds status Windows builds status MacOS builds status

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

  • g++5.5 or more recent. It is known not to work with some older g++5 versions.
  • clang++6.0 or more recent. It should work with clang++ versions all the way back to 3.8, but the CI pipeline doesn't have test for those anymore.
  • Visual Studio 2019 version 16.8.3 or more recent, only with /permissive-. A few features are still unavailable.
  • The versions of MinGW-w64 and AppleClang equivalent to the compilers mentioned above.
  • Clang is notably tested with both libstdc++ and libc++.

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

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

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


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

Even though some parts of the library are original research and some others correspond to custom and rather naive implementations of standard sorting algorithms, cpp-sort also reuses a great deal of code and ideas from open-source projects, often altered to integrate seamlessly into the library. Here is a list of the external resources used to create this library. I hope that the many 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 by insertion_sorter and pdq_sorter come from Orson Peters' pattern-defeating quicksort. Some parts of the benchmarks come from there as well.

  • The algorithm used by tim_sorter comes from Goro Fuji's (gfx) implementation of a Timsort.

  • The three algorithms used by spread_sorter come from Steven Ross Boost.Sort module.

  • utility::as_function, utility::static_const, and several projection-enhanced helper algorithms come from Eric Niebler's Range v3 library. Several ideas such as proxy iterators, customization points and projections, as well as a few other utility functions also come from that library or from the related articles and standard C++ proposals.

  • The algorithm used by ska_sorter comes from Malte Skarupke's implementation of his own ska_sort algorithm.

  • The algorithm used by drop_merge_sorter comes from Adrian Wielgosik C++ reimplementation of Emil Ernerfeldt's drop-merge sort.

  • Many enhanced standard algorithms are directly adapted from their counterparts in libc++, enhanced to handle both projections and proxy iterators.

  • The library internally uses an inplace_merge function that works with forward iterators. Its implementation uses a merge algorithm proposed by Dudziński and Dydek, and implemented by Alexander Stepanov and Paul McJones in their book Elements of Programming.

  • The inplace_merge overload for random-access iterators uses the Symmerge algorithm proposed by Pok-Son Kim and Arne Kutzner in Stable Minimum Storage Merging by Symmetric Comparisons when there isn't enough memory available to perform an out-of-place merge.

  • The implementation of Dijkstra's smoothsort used by smooth_sorter has been directly adapted from Keith Schwarz's implementation of the algorithm.

  • The algorithm used by wiki_sorter has been adapted from BonzaiThePenguin's WikiSort.

  • The algorithm used by grail_sorter has been adapted from Mrrl's GrailSort.

  • The algorithm used by indirect_adapter with forward or bidirectional iterators is a slightly modified version of Matthew Bentley's indiesort.

  • The implementation of the random-access overload of nth_element used by some of the algorithms comes from Danila Kutenin's miniselect library and uses Andrei Alexandrescu's AdaptiveQuickselect algorithm.

  • The algorithms 0 to 16 used by sorting_network_sorter have been generated with Perl's Algorithm::Networksort module.

  • The algorithm 17 used by sorting_network_sorter correspond to the ones found by Symmetry and Evolution based Network Sort Optimization (SENSO) published in Using Symmetry and Evolutionary Search to Minimize Sorting Networks by Valsalam and Miikkulainen.

  • The algorithms 18 to 26 and 28 used by sorting_network_sorter have been found and proposed for inclusion by Bert Dobbelaere with his SorterHunter project. Huge thanks for this contribution :) You can find a full list of most well-known sorting networks up to 32 inputs on his website.

  • Some of the optimizations used by sorting_network_sorter come from this discussion on StackOverflow and are backed by the article Applying Sorting Networks to Synthesize Optimized Sorting Libraries.

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

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

  • The CMake tools embedded in the projects include scripts from RWTH-HPC/CMake-codecov and Crascit/DownloadProject.

  • Some of the benchmarks use a colorblind-friendly palette developed by Thøger Rivera-Thorsen.

  • auto return type

    auto return type

    Hi, more a question than an issue. I stumbled upon you repo while doing some research about, well, sorting algorithms obviously. A bit of "reviewing" lead me to encounter a lot declarations in your code similar to:

    auto sort(Iterable&& iterable) -> void

    I failed to find any technical reason that would lead me to use the auto keyword here and not to specify the return type directly in this kind of cases (and on a more subjective note it hurts a bit!), but I thought I may have missed something. So is it purely out of aesthetic/cosmetic reasons?

    opened by polyvertex 21
  • Optimization for GrailSort

    Optimization for GrailSort

    Hey Morwenn,

    Grail Sort is looking great!

    I actually found an optimization for it about 2 days ago, and it's verified to be working. The algorithm is now 3-4% faster on average now, and all that it took was a little trick with recursion that I learned from Mr. Astrelin's other algorithm, SqrtSort. It's located in the grail_common_sort method, after the insertion sort for small arrays block.

    • John

    EDIT: Scratch the above, thanks for pointing out the change in space complexity. Perhaps the changes to Insertion Sort will still be nice to implement?

        private void grailInsertSort(SortType[] arr, int pos, int len) {
            for(int i = 1; i < len; i++) {
                int insertPos = grailBinSearch(arr, pos, pos + i, pos + i, false);
                if(insertPos < i) {
                    SortType item = arr[pos + i];
                    int shifts = (pos + i) - insertPos;
                    switch(shifts) {
                        case 2:  arr[insertPos + 2] = arr[insertPos + 1];
                        case 1:  arr[insertPos + 1] = arr[insertPos];
                        default: System.arraycopy(arr, insertPos, arr, insertPos + 1, shifts);
                    arr[insertPos] = item;
    opened by MusicTheorist 17
  • asan issue with Clang 6 and std::stable_sort w/ indirect_adapter

    asan issue with Clang 6 and std::stable_sort w/ indirect_adapter

    Asan finds a stack buffer overflow with the following test and the std::stable_sort equivalent:

    Test #135: every sorter with indirect adapter - cppsort::std_sorter

    I've no idea why. Instinctively I would say that it's linked to projection_compare because std_sorter has to use if, but it could also be linked to the new indirect_adapter that accepts projection-only sorters. It's probably a mix of both, but I can't find the actual issue.

    Here is the failing job issue with the full asan log:

    bug help wanted 
    opened by Morwenn 15
  • Multiple variable definition with Clang 9

    Multiple variable definition with Clang 9

    When compiling with Clang 9, I got

    multiple definition of `cppsort::detail::iterator_category_value<std::__1::input_iterator_tag>'
    multiple definition of `cppsort::detail::iterator_category_value<std::__1::forward_iterator_tag>'
    multiple definition of `cppsort::detail::iterator_category_value<std::__1::bidirectional_iterator_tag>'
    multiple definition of `cppsort::detail::iterator_category_value<std::__1::random_access_iterator_tag>'

    because it seems that Clang 9 does not treat template specializations of constexpr variables inline anymore. Because the library is in C++14, the specializations cannot be marked inline so I think they should be static instead.

    opened by Dwarfobserver 11
  • Support Conan package (#121)

    Support Conan package (#121)


    I just updated few points:

    • Added compiler validation for MSVC. If Visual Studio is present, Conan will raise an exception.
    • Copied license file to package folder.
    • C++14 as required to build test_package
    • Added Conan job on Travis. This job only will be executed on master branch. Also, the same job will upload the package to bintray after to create the package. It's necessary to fill the env var CONAN_PASSWORD on your Travis settings. The password is your Bintray API Key.


    opened by uilianries 9
  • Smaller sorting networks for 20, 23 and 24 inputs

    Smaller sorting networks for 20, 23 and 24 inputs

    Hi Morwenn,

    I understood you were interested in further reduced sorting network sizes. I did some personal research on the subject and can contribute the following networks. All three are AFAIK networks with the smallest number of pairs at this time for their number of inputs. Please verify correctness before integrating them.

    Kind regards, Bert Dobbelaere.

    Network for N=20, size=91, depth=12: [ [(0, 3), (1, 7), (2, 5), (4, 8), (6, 9), (10, 13), (11, 15), (12, 18), (14, 17), (16, 19)] , [(0, 14), (1, 11), (2, 16), (3, 17), (4, 12), (5, 19), (6, 10), (7, 15), (8, 18), (9, 13)] , [(0, 4), (1, 2), (3, 8), (5, 7), (11, 16), (12, 14), (15, 19), (17, 18)] , [(1, 6), (2, 12), (3, 5), (4, 11), (7, 17), (8, 15), (13, 18), (14, 16)] , [(0, 1), (2, 6), (7, 10), (9, 12), (13, 17), (18, 19)] , [(1, 6), (5, 9), (7, 11), (8, 12), (10, 14), (13, 18)] , [(3, 5), (4, 7), (8, 10), (9, 11), (12, 15), (14, 16)] , [(1, 3), (2, 4), (5, 7), (6, 10), (9, 13), (12, 14), (15, 17), (16, 18)] , [(1, 2), (3, 4), (6, 7), (8, 9), (10, 11), (12, 13), (15, 16), (17, 18)] , [(2, 3), (4, 6), (5, 8), (7, 9), (10, 12), (11, 14), (13, 15), (16, 17)] , [(4, 5), (6, 8), (7, 10), (9, 12), (11, 13), (14, 15)] , [(3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14), (15, 16)] ]

    Network for N=23, size=116, depth=14 : [ [(0, 12), (1, 7), (2, 8), (3, 17), (4, 9), (5, 13), (6, 20), (10, 18), (14, 19), (15, 21), (16, 22)] , [(0, 5), (1, 16), (2, 15), (3, 4), (6, 14), (7, 22), (8, 21), (9, 17), (10, 11), (12, 13), (19, 20)] , [(0, 3), (4, 5), (6, 10), (7, 15), (8, 16), (9, 12), (11, 14), (13, 17), (18, 19)] , [(3, 11), (4, 10), (5, 14), (9, 18), (12, 20), (13, 19)] , [(2, 3), (8, 11), (12, 15), (20, 21)] , [(1, 3), (2, 6), (7, 12), (11, 16), (17, 21), (20, 22)] , [(0, 1), (3, 8), (7, 11), (12, 16), (15, 20), (17, 22)] , [(0, 2), (1, 6), (3, 9), (4, 7), (5, 15), (8, 18), (10, 12), (11, 13), (14, 20), (16, 19)] , [(1, 3), (2, 4), (5, 10), (6, 9), (8, 11), (12, 15), (13, 18), (14, 17), (19, 21), (20, 22)] , [(1, 2), (3, 4), (5, 6), (7, 11), (9, 10), (12, 16), (13, 14), (17, 18), (19, 20), (21, 22)] , [(2, 3), (6, 8), (7, 9), (10, 11), (12, 13), (14, 16), (15, 17), (20, 21)] , [(4, 7), (5, 6), (8, 9), (10, 12), (11, 13), (14, 15), (16, 19), (17, 18)] , [(4, 5), (6, 7), (8, 10), (9, 12), (11, 14), (13, 15), (16, 17), (18, 19)] , [(3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14), (15, 16), (17, 18), (19, 20)] ]

    Network for N=24, size=121, depth=14: [ [(0, 12), (1, 7), (2, 8), (3, 17), (4, 9), (5, 13), (6, 20), (10, 18), (11, 23), (14, 19), (15, 21), (16, 22)] , [(0, 5), (1, 16), (2, 15), (3, 4), (6, 14), (7, 22), (8, 21), (9, 17), (10, 11), (12, 13), (18, 23), (19, 20)] , [(0, 3), (4, 5), (6, 10), (7, 15), (8, 16), (9, 12), (11, 14), (13, 17), (18, 19), (20, 23)] , [(3, 11), (4, 10), (5, 14), (9, 18), (12, 20), (13, 19)] , [(2, 3), (8, 11), (12, 15), (20, 21)] , [(1, 3), (2, 6), (7, 12), (11, 16), (17, 21), (20, 22)] , [(0, 1), (3, 8), (7, 11), (12, 16), (15, 20), (22, 23)] , [(0, 2), (1, 6), (3, 9), (4, 7), (5, 15), (8, 18), (10, 12), (11, 13), (14, 20), (16, 19), (17, 22), (21, 23)] , [(1, 3), (2, 4), (5, 10), (6, 9), (8, 11), (12, 15), (13, 18), (14, 17), (19, 21), (20, 22)] , [(1, 2), (3, 4), (5, 6), (7, 11), (9, 10), (12, 16), (13, 14), (17, 18), (19, 20), (21, 22)] , [(2, 3), (6, 8), (7, 9), (10, 11), (12, 13), (14, 16), (15, 17), (20, 21)] , [(4, 7), (5, 6), (8, 9), (10, 12), (11, 13), (14, 15), (16, 19), (17, 18)] , [(4, 5), (6, 7), (8, 10), (9, 12), (11, 14), (13, 15), (16, 17), (18, 19)] , [(3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14), (15, 16), (17, 18), (19, 20)] ]

    opened by bertdobbelaere 9
  • Conan package

    Conan package

    Hello @Morwenn ! Do you know about Conan? Conan is modern dependency manager for C++. And will be great if your library will be available via package manager for other developers.

    Here you can find example, how you can create package for the library.

    If you have any questions, just ask :-)

    opened by zamazan4ik 8
  • gcc 5.2.0 segfaults when compiling `#include <cpp-sort/sorters.h>`

    gcc 5.2.0 segfaults when compiling `#include `

    How to reproduce (paths were altered for security concerns):

    # echo '#include <cpp-sort/sorters.h>' > single.cpp
    # g++ -I/path/to/cpp-sort/1.6.0/include -std=gnu++14 single.cpp -o single.o
    In file included from /path/to/cpp-sort/1.6.0/include/cpp-sort/sorters/default_sorter.h:32:0,
                     from /path/to/cpp-sort/1.6.0/include/cpp-sort/sorters.h:32,
                     from single.cpp:1:
    /path/to/cpp-sort/1.6.0/include/cpp-sort/adapters/self_sort_adapter.h:159:21: internal compiler error: Segmentation fault
    0xaa09af crash_signal
    0x642565 dependent_template_arg_p
    0x6426ae check_instantiated_arg
    0x6428fc check_instantiated_args
    0x6586a5 instantiate_template_1
    0x6586a5 instantiate_template(tree_node*, tree_node*, int)
    0x6e28e7 finish_id_expression(tree_node*, tree_node*, tree_node*, cp_id_kind*, bool, bool, bool*, bool, bool, bool, bool, char const**, unsigned int)
    0x695be4 cp_parser_primary_expression
    0x69809d cp_parser_postfix_expression
    0x69a389 cp_parser_unary_expression
    0x69aec7 cp_parser_binary_expression
    0x69b4cd cp_parser_assignment_expression
    0x69b8a3 cp_parser_constant_expression
    0x6a1b3e cp_parser_template_argument
    0x6a1b3e cp_parser_template_argument_list
    0x6a1b3e cp_parser_enclosed_template_argument_list
    0x6a2756 cp_parser_template_id
    0x6a2e56 cp_parser_class_name
    0x699036 cp_parser_qualifying_entity
    0x699036 cp_parser_nested_name_specifier_opt
    Please submit a full bug report,
    with preprocessed source if appropriate.
    Please include the complete backtrace with any bug report.
    See <> for instructions.
    opened by FelipeLema 7
  • Review for inclusion request in conan-center@bintray

    Review for inclusion request in conan-center@bintray

    Hi Morwenn,

    I've been checking this inclusion request and everything looks ok with the conan recipe for this header only library, so congratulations!!!

    I've followed the contribution guidelines and I only have a few comments about the package information reported in bintray

    Please add the following changes in your bintray package:

    • Better description for the package:
      • currently: Additional sorting algorithms & related tools
      • proposed: Additional sorting algorithms for C++14 and C++17
    • Set the following fields in Bintray:
      • Image (if available)
      • Website
      • Issue Tracker
      • Product Maturity
    • Search tags for Bintray (optional)

    As an example you can have a look at boost package which is reporting this information.

    Thank you for your contribution, Pedro

    opened by pvicente 7
  • Add undefined behaviour sanitizer

    Add undefined behaviour sanitizer

    While Valgrind is pretty cool, there can't be too many tools checking for potential undefined behaviour. We could add the undefined behaviour sanitizer to the Debug mode:

    • [x] Don't use it with MinGW since it is not supported.
    • [x] Use it with GCC on Linux.
    • [x] Use it with Clang on Linux.

    Unfortunately, it doesnt "just" work with Clang. hen I try to add -fsanitize=undefined, I get the following error:

    Linking CXX executable cpp-sort-testsuite
    /usr/bin/ld: cannot find /usr/lib/llvm-3.8/bin/../lib/clang/3.8.0/lib/linux/libclang_rt.ubsan_standalone-x86_64.a: No such file or directory
    /usr/bin/ld: cannot find /usr/lib/llvm-3.8/bin/../lib/clang/3.8.0/lib/linux/libclang_rt.ubsan_standalone_cxx-x86_64.a: No such file or directory
    clang: error: linker command failed with exit code 1 (use -v to see invocation)
    make[2]: *** [testsuite/cpp-sort-testsuite] Error 1
    make[1]: *** [testsuite/CMakeFiles/cpp-sort-testsuite.dir/all] Error 2
    make: *** [all] Error 2

    It feels like some files are missing from the Linux VM on Travis, but I can't confirm for sure... Any help to solve this issue is welcome :)

    enhancement tooling 
    opened by Morwenn 7
  • Improve Documentation for Users

    Improve Documentation for Users

    As everyone who's looking for the 'fastest sorter' knows, there's no universal answer, and the only way to find out what works best for any given situation is to try things and benchmark them. This project is a great resource for that! It provides access to a huge array of sorters, and the universal interfaces make it very easy to wrap up a range of implementations into a common interface, to assist with batch testing.

    However. While very well documented compared to most github projects, there's a clear focus here on developers wishing to add their new algorithm into the framework. For the less expert layperson simply wishing to run the existing algorithms, a few examples would go a long way (especially thanks to the common interfaces). But those examples are unfortunately missing. I've been struggling for a while now to figure out how to actually use the indirect_adapter to sort a c-style array of objects. I can provide a projector method, or a lamdba, or a functor, or whatever is required.... but i don't know what's required. The documentation describes what it is, and how it works, but not how to use it. The only snippet of code is

    template<typename Sorter>
    class indirect_adapter;

    which isn't relevant for me as i'm not using c++17, and ... well it just declares a template typename that doesn't get used, and a class. I don't even know what this is supposed to be telling me. Going from the example of the hybrid adapter on the homepage I tried (among many other things)

        cppsort::indirect_adapter< cppsort::pdq_sorter > sorter;
        MyObject* objects = new MyObjects[20000];
        ... fill array ...
        sorter(objects, objects+20000, std::greater<>{}, &MyObject::Get_Time);

    but I just get a wall of template errors. The same happens with

       sorter(objects, objects+20000, [](const MyObject& obj){ return obj.Get_Time();} );


       sorter(objects, objects+20000, [](const MyObject& obj_a, const MyObject& obj_b){ return obj_a.Get_Time() < obj_b.Get_Time(); } );

    Some of these sorters handle containers rather than ranges, for which it seems that using a sorter facade is required (which is again, not especially clear from the documentation), so i've also tried putting one of those into the adapter, but again no luck. I'm clearly shooting in the dark here.

    Providing even a single example for each functionality would go a long way.

    opened by marc1uk 6
  • Metrics


    Currently we've got measures of presortedness to analyze the collections to sort, but no module to analyze how sorters perform except for counting_adapter. Which is actually a shame since I am the first one to use such metrics when I need to show how much algorithms have improved in release notes. Historically I've used the following metrics to analyze algorithms:

    • Total running rime
    • Cycles per element
    • Number of comparisons
    • Number of projections
    • Number of moves

    The simplest design would be for metrics to be sorter adapters, with a twist allowing them to combine their results into some kind of generic tuple with named accessors (the original Ranges TS had such an extension to tuple, I could look into that, it would be yet another partial solution to #134). Said tuple should be printable, in which case it would display the information it gathered.

    All metrics would go in a cppsort::metric namespace, and the individual files would go in cpp-sort/adapters/metrics, with or without a metrics.h file allowing to include them all.

    To make metrics more usable, a combine_metrics utility could be introduced, allowing to write something along these lines:

    template<typename Sorter>
    using add_metrics_to = cppsort::combine_metrics<
    auto my_sort = add_metrics_to(cppsort::quick_sort);
    auto metrics = my_sort(my_collection);
    std::cout << metrics;

    I believe that those metrics can mostly be implemented in a non-intrusive way, though the moves counter might be trickier to get right.

    opened by Morwenn 0
  • Remodel pipe support for projections after P2387

    Remodel pipe support for projections after P2387

    P2387 describes the different strategies to implement operator| for range adaptors. The support for operator| for projections in cpp-sort is already extremely similar and could certainly benefit from the more mature solution proposed in the paper.

    The simplest way to change the design is probably a clean breaking change, capitalizing on the fact that cpp-sort 2.0 is on tracks and will eventually be released.

    opened by Morwenn 0
  • Simple sorter options

    Simple sorter options

    Lots of sorters in the library have constexpr variables corresponding to various options:

    • drop_merge_sort has double_comparison and recency.
    • Lots of sorters have a size threshold under which they use another algorithm to sort small collections.
    • spread_sort has a slew options configuring bucket size and whatnot

    All those options currently exist as details and are forced at compile time, but users have no control over them. I would like to expose several of these options so that users can change them freely. A simple way would be to create foobar_sorter_options objects, simple structs that can be passed to sorters at compile time thanks to NTTP.

    Here is an example of what it could look like for drop_merge_sort:

    constexpr cppsort::drop_merge_sorter_options options = {
        .recency = 8,
        .double_comparison = true
    auto sort = cppsort::drop_merge_sorter<options>{};


    constexpr cppsort::drop_merge_sorter_options options = ;
    auto sort = cppsort::drop_merge_sorter<{
        .recency = 8,
        .double_comparison = true

    The combination of NTTP and designated initializers would allow to pass all simple options in an option structure while naming them, which is IMO a superior solution to a sea of unnamable template parameters.

    List of affected sorters and options.:

    • adaptive_shivers_sort: ???
    • cartesian_tree_sort: ???
    • counting_sort: ???
    • drop_merge_sort
      • double_comparison (bool, default true): TODO
      • recency (int, default 8): TODO
    • float_spread_sort: ???
    • grail_sort: ???
    • heap_sort: ???
    • insertion_sort: ???
    • integer_spread_sort: ???
    • mel_sort: ???
    • merge_insertion_sort: ???
    • merge_sort: ???
    • pdq_sort:
      • insertion_sort_threshold (int, default 24): partitions below this size are sorted using insertion sort.
      • ninther_threshold (int, default 128): partitions above this size use Tukey's ninther to select the pivot.
      • partial_insertion_sort_limit (int, default 8): when we detect an already sorted partition, attempt an insertion sort that allows this amount of element moves before giving up.
      • block_size (int, default 64): must be multiple of 8 due to loop unrolling, and < 256 to fit in unsigned char.
      • cacheline_size (int; default 64): cacheline size, assumes power of two.
    • poplar_sort: ???
    • quick_merge_sort:
      • Size before switching to small sort (int)
    • quick_sort: ???
    • selection_sort: ???
    • ska_sort: ???
    • slab_sort: ???
    • smooth_sort: ???
    • spin_sort: ???
    • split_sort: ???
    • spread_sort: ???
    • std_sort: nothing
    • string_spread_sort: ???
    • tim_sort: ???
    • verge_sort: ???
    • wiki_sort: ???

    The list in the previous section is almost empty at the time of writing these words, and yet it already highlights some issues and design decisions to take into account:

    • Several configuration constant are currently of type difference_type. This is a problem when passing options to the sorter because difference_type is only known when the iterator type is known, which happens after template instantiation. Passing options to the sorter itself means that these options should be agnostic of the iterator type. For now I think that using int for what should always be small constants should be consensual enough, especially since difference_type is assumed to be constructible from int.
    • Buffered sorters already have a template parameter, options would likely go second.
    • Some sorters have different size limits before switching to a small collection sort. Either just go with forward_small_sort_limit, bidirectional_small_sort_limit, or invent a mechanism accepting an iterator tag and with a default option (can always default to forward iterator tag I guess).
    • Spread sorters will likely have some compatible and some non-compatible options: have a shared options structure and more options structures inheriting from the main one.
    • Pass more complicated options to the sorter's constructor? Anything with mutable parameters should go down that road.
    • Sorter adapters could likely have options too when it makes sense. Options are embedded in the template parameter of the adapted sorter, so that problem is at least a solved one.
    • We can probably reuse some option objects to pass nested compile time options the following way (assuming pdq_sorter_options object is used):
      constexpr cppsort::drop_merge_sorter_options options = ;
      auto sort = cppsort::drop_merge_sorter<{
          .recency = 8,
          .double_comparison = true,
          .pdq_sort_options = {
              .insertion_sort_threshold = 24,
              .ninther_threshold = 128
    opened by Morwenn 0
  • Document adaptive sorter

    Document adaptive sorter

    Document which of the library's sorters are adaptive with regard to which measure of presortedness.

    Several questions:

    • Make a list?
    • Make a box? (a box with ✅/❌ would look cool)
    • If a sorter is Enc-adaptive, do we need to mention that it's also Runs-adaptive? (yes if box)
    • Include the MOPs we don't implement? (yes)
    • How can we make sure that our algorithms are correctly implemented to be MOP-adaptive?
    opened by Morwenn 0
  • Upgrade to C++23

    Upgrade to C++23

    Still lots of time before actually getting to that issue, especially since there's the whole C++20 thing (#112) and 2.0.0 version to handle first, so this is more of a wish list for a distant future. The first step will likely be to conditionally support some features to 2.x.y at some point, and even to 1.x.y when it makes sense and it's not too difficult, then the rest will be nice things to have if there's ever a breaking change post 2.0.0.

    This issues list can be used to track papers that were plenary approved for C++23.

    Conditionally support back to 1.x.y

    • [[assume]] as the preferred implementation for CPPSORT_ASSUME when available.
    • There might be uses for std::stacktrace, I need to investigate.
    • TODO

    Conditionally support back to 2.x.y

    • std::allocator::allocate_at_least
    • TODO

    Features for the next breaking change

    • Deducing this will finally allow a way forward to implement mutable sorters (issue #104).
    • Deducing this for various function adapters.
    • auto(x) can replace CPPSORT_AUTO_CAST in <cpp-sort/mstd/ranges.h>.
    • auto(x) for apply_permutation tests, update doc accordingly.
    • if consteval might help with the constexpr algorithms.
    • std::unreachable() surely has its uses in places.
    • constexpr std::unique_ptr, <cmath>, <cstdlib> (issue #58).
    • Support for fixed-width floating point types.
    • How can we support static operator()? It sounds tricky enough.
    • static constexpr variables in constexpr functions for better codegen?
    • TODO

    Considering that I still haven't probably started work on 2.x.y, the version might end up targeting C++23 instead of C++20.

    opened by Morwenn 0
  • Revamp buffer providers

    Revamp buffer providers

    Currently the user-facing buffer providers suffer from poor decisions from the early days: they default-construct a buffer of elements, then the algorithms using buffer providers move elements to those. This design has a few issues:

    • Buffered sorters don't work with elements that are not default-constructible.
    • When the types are default-constructible but the operation is not trivial, we pay the cost of default construction for every element of the buffer, no matter whether it ends up being used or not.
    • Building a compatible buffer provider that allows default-constructible types would incur some additional overhead (see #59).

    I think that the right solution is to let the buffer providers allocate the storage for enough elements, but the buffered sorters should construct and destroy the elements in the buffer as needed instead of just performing moves. This would definitely be a breaking change, so it's not something to do on the branch 1.x, but rather something to plan for 2.0.0.

    The new design makes the new buffer providers look awfully like allocators, but a few design differences might make them too difficult to use properly with allocators, so I don't really want to merge them unless there is a well-motivated demand for it.

    opened by Morwenn 0
  • 1.14.0(Dec 18, 2022)


    I am writing those lines shortly after coming back from the local ramen restaurant, where I had the pleasure to enjoy edamame and tantanmen for the first time in a while. After eight months and and two patch releases, the long-awaited cpp-sort 1.14.0 is finally out. One of the reasons already mentioned in previous release notes is the work on version 2.0.0, which is far from being ready, but already had a positive effect on the overall quality of the library.

    Worry not, for this long time spent in the making was not in vain: this version brings more new features to the table than usual with a clear focus on orthogonality, allowing to make the most of existing features. Another highlight of this release is a focus on documentation: I tried to make it more amenable with new power words, a lots of small changes and also a new quickstart page.

    New features

    New adapters: split_adapter and drop_merge_adapter (#148)

    split_adapter: the library has shipped split_sorter since version 1.4.0, a sorter base don an algorithm that works by isolating an approximation of a longest non-decreasing subsequence in a O(n) pass in the left part of the collection to sort, and the out-of-place elements in the right part of the collection. The right part is then sorted with pdq_sort, and both parts are merged together to yield a sorted collection.

    split_adapter is basically the same, except that it accepts any bidirectional sorter to replace pdq_sort in the algorithm. As such it acts as a pre-sorting algorithm that can be plugged on top of any compatible sorter to make it Rem-adaptive.

    drop_merge_adapter: this is the adapter version of drop_merge_sorter, allowing to pass in any sorter instead of relying on pdq_sort. Much like SplitSort, drop-merge sort works by isolating out-of-place elements, sorting them with another sorting algorithm, and merging them back together. Unlike SplitSort it places the out-of-place elements in a contiguous memory buffer, allowing to use any sorter to sort them.

    While philosophically close from each other, the two algorithms use different heuristics to isolate out-of-place elements, leading to a different behaviour at runtime: for the same fallback algorithm, drop_merge_adapter is faster than split_sorter when there are few out-of-place elements in the collection to sort, but becomes slower when the number of out-of-place elements grows.

    Graph showing the speed difference between heap_sort raw, then adapted with split_adapter and drop_merge_adapter, when the number of inversions in the vector to sort increases

    Graph showing the speed difference between quick_sort raw, then adapted with split_adapter and drop_merge_adapter, when the number of inversions in the list to sort increases

    As can be seen in the benchmarks above, split_adapter and drop_merge adapter offer different advantages: split_adapter takes a bit less advantage of existing presortedness than drop_merge_adapter, but its cost it very small even when there are lots of inversions. This can be attributed to drop_merge_adapter allocating memory for the out-of-place elements while split_adapter does everything in-place.

    When sorting a std::list however, drop_merge_adapter becomes much more interesting because the allocated memory allows to perform the adapted sort into a contiguous memory buffer, which tends to be faster.

    New utilities: sorted_indices and apply_permutation (#200)

    utility::sorted_indices is a function object that takes a sorter and returns a new function object. This new function object accepts a collection and returns an std::vector containing indices of elements of the passed collection. These indices are ordered in such a way that the index at position N in the returned vector corresponds to the index where to find in the original collection the element that would be at position N in the sorted collection. It is quite similar to numpy.argsort.

    std::vector<int> vec = { 6, 4, 2, 1, 8, 7, 0, 9, 5, 3 };
    auto get_sorted_indices_for = cppsort::utility::sorted_indices<cppsort::smooth_sorter>{};
    auto indices = get_sorted_indices_for(vec);
    // Displays 6 3 2 9 1 8 0 5 4 7
    for (auto idx: indices) {
        std::cout << *it << ' ';

    utility::apply_permutation accepts a collection, and permutes it according to a collection of indices in linear time. It can be used together with sorted_indices to bring a collection in sorted order in two steps. It can even be used to apply the same permutation to several collections, allowing to deal with structure-of-array patterns where the information is split in several collections.

    // Names & ages of persons, where the identity of the person is the
    // same index in both collections
    std::vector<std::string> names = { /* ... */ };
    std::vector<int> ages = { /* ... */ };
    auto get_sorted_indices_for = cppsort::utility::sorted_indices<cppsort::poplar_sorter>{};
    auto indices = get_sorted_indices_for(names); // Get sorted indices to sort by name
    // Bring persons in sorted order
    cppsort::utility::apply_permutation(names, auto(indices));
    cppsort::utility::apply_permutation(ages, indices);

    Note the use of C++23 auto() copy above: apply_permutation mutates both of the collections it accepts, so the indices have to be copied in order to be reused.

    New utilities: sorted_iterators and indirect (#42, #200)

    utility::sorted_iterators is a function object that takes a sorter and returns a new function object. This new function object accepts a collection and returns an std::vector containing iterators to the passed collection in a sorted order. It can be thought of as a kind of sorted view of the passed collection - as long as said collection does not change. It can be useful when the order of the original collection must be preserved, but operations have to be performed on the sorted collection.

    std::list<int> li = { 6, 4, 2, 1, 8, 7, 0, 9, 5, 3 };
    auto get_sorted_iterators_for = cppsort::utility::sorted_iterators<cppsort::heap_sorter>{};
    const auto iterators = get_sorted_iterators_for(li);
    // Displays 0 1 2 3 4 5 6 7 8 9
    for (auto it: iterators) {
        std::cout << *it << ' ';

    The new projection indirect dereferences its parameter and returns the result. It can be used together with standard range algorithms to perform operations on the vector of iterators returned by sorted_iterators.

    std::forward_list<int> fli = /* ... */;
    auto get_sorted_iterators_for = cppsort::utility::sorted_iterators<cppsort::poplar_sorter>{};
    const auto iterators = get_sorted_iterators_for(fli);
    auto equal_bounds = std::ranges::equal_range(iterators, 42, {}, cppsort::utility::indirect{});

    New sorter: d_ary_heap_sorter

    d_ary_heap_sorter implements a heapsort variant based on a d-ary heap, a heap where each node has D children - instead of 2 for a binary heap. This number of children nodes can be passed as an integer template parameter to the sorter and its associated sort function. Storing more nodes makes the algorithm a bit more complicated but improves the locality of reference, which can affect execution speed.

    std::vector<int> vec = { /* ... */ };
    cppsort::d_ary_heap_sort<4>(vec); // d=4

    The complexity is the same as that of the library's heap_sorter. It is however worth nothing that unlike its binary counterpart, d_ary_heap_sorter does not implement a bottom-up node searching strategy.

    Benchmark showing the difference in cycles per elements when sorting a one-million element vector with either heap_sort or several flavours of d_ary_heap_sort with different values for D

    The benchmark above shows how the value picked for D might influence the speed of the algorithm. It also shows that d_ary_heap_sort is currently much slower than heap_sort, though the former is not really optimized and has room for improvements.

    Bug fixes

    • Fixed slab_sort when sorting collections where several elements compare equivalent to the median element (#211).
    • Fixed a potential use-after-move bug in quick_merge_sort.


    Algorithmic & speed improvements:

    • slab_sort now falls back to using insertion sort on small enough collections in its melsort pass. This change leads to speed improvements when sorting shuffled data that does not exhibit obvious patterns. Benchmark showing the speed of slab_sort for different data patterns of one million double elements in cpp-sort 1.13.2 vs 1.14.0
    • low_moves_sorter<n>: removed O(n) comparisons in the generic case. Benchmark showing the difference in speed of low_moves_sorter when sorting 1 to 30 shuffled elements in cpp-sort 1.13.2 vs 1.14.0

    Other improvements:

    • Add more audit assertions around some internal merge operations. Audits are expensive assertions which can be enabled by defining the preprocessor macro CPPSORT_ENABLE_AUDITS.
    • When CPPSORT_ENABLE_AUDITS is defined, the library's internal assumptions (e.g. __builtin_assume) are now turned into assertions, providing additional checks to diagnose errors.
    • schwarz_adapter<schwarz_adapter<Sorter>> is now functionally equivalent to schwarz_adapter<Sorter>, save for the parameters accepted by the constructor. It makes it actually work for more than just a few accidentally valid cases.
    • operator| for projections was changed as follows: when one of the operators is utility::identity or std::identity, it returns the other projection directly.



    • Added a quickstart page to the documentation (#203).
    • Added a note to the library nomenclature page, making it explicit that words that appear in italics all over the documentation refer to words or power described in that page.
    • Added new power words to the library nomenclature:
      • Unified sorting interface
      • Equivalent elements
    • Added notes about utility::size, utility::iter_move and utility::iter_swap being removed in cpp-sort 2.0.0.
    • Removed a note about probe::max being noticeably slower on bidirectional and forward iterators. This note was there because of calls to std::distance that could potentially be linear, potentially changing the documented complexity of the algorithm. I reviewed the algorithm and realized that those calls were always performed on random-access iterators and thus in O(1) time, making the note unneeded.
    • Regenerated the Small array sorters section of the benchmarks page, which did not reflect recent changes and additions to small array sorters.


    • Improvements to the small-array benchmark:
      • The labels can now contain spaces.
      • Compute and display cycles per element instead of total number of cycles.
      • Display the median of the results for a given collection size instead of the average.
      • Let matplotlib choose the best position for the legend to appear.
      • Generate results for merge_exchange_network_sorter.
      • Don't generate benchmarks for collections of size 0.
    • Small improvements to the inversions benchmark:
      • The labels can now contain spaces.
      • The legend preserves the order of the sorters used in the C++ file.
      • Move average computation to the python file.


    • Improved forward compatibility of with Conan v2. The library now requires a more recent Conan version to be packaged.
    • Bump the Catch2 version downloaded by the test suite to v3.2.1.

    Known bugs

    I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.

    Source code(tar.gz)
    Source code(zip)
  • 1.13.2(Oct 9, 2022)


    This release is named after the eponymous song in the OST of The Legend of Zelda: Link's Awakening. This theme, following you for a short time at the very beginning of the game, never fails to haunt me and put me in a nostalgic mood, be it the original, the Switch remake or fan remakes. It's like the mood, the feels, the adventure are all still there deep down somewhere and forever.

    This is the first cpp-sort version benefiting of a second patch release for a simple reason: I just made the library compatible with clang-cl. For those who don't know, clang-cl is a Clang fronted on MSVC, which also has the particularity of using the Microsoft STL instead of libc++. I only tested clang-cl recently, but I believe it worked in version 1.13.0 and I introduced a small change that broke it in version 1.13.0, hence a new patch version to fix that and introduce official support for this target.


    No new features or algorithmic changes, this release is all about tooling:

    • Make the test suite pass with clang-cl (#208). There are still lots of warnings, but they are mostly noise.
    • Add clang-cl to continuous integration. Currently only the Debug mode is tested with clang-cl in the CI: the Release mode crashes due to what I think is an out-of-memory error in the VM, but I did compile & run it locally and it worked correctly.
    • Improve std::identity detection with Clang and clang-cl in C++20 mode.
    • Add a Python script to the tools folder to make it easier to change the version number where needed before a release.
    • Make more compatible with Conan 2.0. It now requires at least Conan 1.50.0 to work.

    Known bugs

    I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.

    Source code(tar.gz)
    Source code(zip)
  • 1.13.1(Oct 2, 2022)


    This release is named after Easily Embarrassed's critically underrated Find Her, a great mix of bounce, crispy synths and glitchy sounds. It seems that I can't ever get bored of it.

    I haven't taken the time to work a lot on cpp-sort lately, which called for at least a small release with the available bug fixes and quality of life changes. While remaining mostly a quality-of-life release, it eventually turned out to be bigger than expected, mostly due to the ongoing work the future version 2.0.0 of the library and the resulting refactors and backports.

    The most notable changes are the algorithmic improvements mentioned in the corresponding section of this note, and the addition of a page explaining how to write a sorter adapter to the documentation.

    Bug fixes

    • Fix iter_move and iter_swap when the library is compiled with C++20. The standard perimeter changed a bit in this area, and caused some ambiguous overload errors when the compiler couldn't decide which overload to pick between the standard library ones and the cppsort::utility:: ones. The standard library ones are now preferred for standard types when they exist.
    • <cpp-sort/sorters/spreadsort/string_spread_sorter.h> could not be included alone due to a missing include. This is now fixed.
    • Fix a bug where make_projection_compare failed to compile when passed an instance of std::identity in C++20 mode. Introduced in version 1.13.0, this bug could cause issues when passing std::identity to sorters relying on sorter_facade to provide projection support, such as std_sorter.
      // Error in 1.13.0, works in 1.13.1
      cppsort::std_sort(collection, std::greater{}, std::identity{});


    Algorithmic & speed improvements:

    • Update heap_sort from upstream (we use the libc++ implementation): the new implementations turns it into a bottom-up heapsort. It performs fewer comparisons than the previous implementation, which doesn't make a noticeable difference from a speed point of view when comparisons are cheap, but can be much more noticeable when comparisons are expensive. This new implementation can be slower in the expensive moves/cheap comparisons scenario. Graph showing the difference of comparisons performed between the old an new versions of heap_sort
    • The fallback of quick_merge_sort for forward iterators when sorting just a few elements was changed from bubble sort to selection sort after I was reminded of the fact that quick_merge_sort was not a stable sort anyway and could therefore switch to a better unstable fallback algorithm for very small collections. Benchmark the new quick_merge_sort over std::forward_list against the old version
    • string_spread_sort was changed to perform fewer projections, sometimes halving the total number of performed projections. Graph showing the difference of projections performed between the old an new versions of string_spread_sort
    • The library's internal adaptive quickselect implementation was tweaked to perform fewer projections. As a result the following sorters perform up to 1% fewer projections when operating on random-access iterators:
    • MSVC STL SIMD algorithms are now used when possible, which might marginally impact the following components for random-access iterators:

    Improvements to sorting networks:

    • All sorting networks used by sorting_network_sorter are now formally verified.
    • Regenerate all sorting_network_sorter specializations with the smallest networks from this list. The main resulting change is that sorting 25 inputs is now done with 130 compare-exchanges instead of 131.
    • All specializations of sorting_network_sorter now have their index_pairs() function marked as [[nodiscard]] when possible.

    Other improvements:

    • Total, weak and partial order comparators now support __int128_t and __uint128_t.
    • hybrid_adapter is now fully constexpr when the sorters it wraps are themselves constexpr (#58).


    • Add a tutorial to the documentation explaining how to write a sorter adapter with a simple example (issue #154).
    • Various smaller changes to improve the overall quality of the documentation.
    • The required and downloaded Catch2 version is now v3.1.0.
    • The from the tools directory was changed by a more complete tool which formally verifies that a given sorting network works, then generates the corresponding sorting_network_sorter.
    • dist::as_long_string in the benchmarking tools now inherits from utility::projection_base and its operator() is const.
    • Continuous integration: update scripts to use actions/checkout v3.
    • The configurations tested by the CI change depending on which tools are available in the CI environments.

    Known bugs

    I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.

    Source code(tar.gz)
    Source code(zip)
  • 1.13.0(Apr 12, 2022)


    A few days ago I went to the swimming pool for the first time since 2015, which might also be the first time since the very first cpp-sort commits. The library is getting old, and while it might be too late to give it a cute name, it is still time to give it a cute logo.

    cpp-sort logo

    This release focuses on improving the state of function objects in the library in a somewhat holistic way, notably with the addition of flip and not_fn, but also with smaller changes:

    • Many more function objects are now transparent or conditionally transparent.
    • Several function objects that except a single parameter now inherit from projection_base, which makes them more easily chainable.
    • Some comparator adapters were updated to automatically unwrap upon recognizing specific function objects, allowing to reduce template nesting and instantiations.
    • The documentation about function objects and related concepts was improved.

    New features

    New comparator adapters not_fn and flip. The former is equivalent to the C++17 std::not_fn: it takes a comparator and returns a function object of type not_fn_t<F> whose call operator calls the adapted comparator and returns the negation of its result. The latter is named after the flip function from Haskell's Prelude module: it takes a comparator and returns a function object of type flip_t<F> whose call opearator calls the adapted comparator with its arguments flipped. Here is an example of them being used to reimplement std::upper_bound in terms of std::lower_bound:

    template<typename ForwardIt, typename T, typename Compare>
    auto upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
        -> ForwardIt
        return std::lower_bound(
            first, last, value,

    The function templates flip and not_fn recognize and unwrap some combinations of flip_t, not_fn_t and other "vocabulary types" in function objects. For example flip(flip(std::less{})) returns an instance of std::less<> instead of flip_t<flip_t<std::less<>>>. The goal is to reduce the nesting of templates as well as the number of templates instantiated by the library — which is especially interesting considering that many of the library's internal functions rely on flip and not_fn.

    New sorter: adaptive_shivers_sort, a k-aware natural mergesort described by Vincent Jugé in Adaptive Shivers Sort: An Alternative Sorting Algorithm. It is very similar to tim_sort and actually shares most of its code. Adaptive ShiversSort worst case notably performs 33% fewer comparisons that timsort's worse case.

    Bug fixes

    • When wrapping a non-comparison sorter that accepts projections (such as spread_sorter), indirect_adapter failed to compile if passed a projection but no comparison (issue #204, thanks to @marc1uk for reporting).




    • The documentation now uses relative links when linking to its own pages instead of absolute links to the online wiki. This makes the documentation more easily browsable in the GitHub repository interface at any point in time.
    • It is also now browsable offline with Gollum (issue #198). A new section of the documentation explains how to do it.
    • Update the documentation about comparators, create a dedicated page comparator adapters.
    • Add a section explaining what transparent function objects are.

    Test suite:

    • Rename the test suite directory from testsuite to tests, in accordance with the Pitchfork project layout.
    • Upgrade Catch2 to v3-preview4.
    • New CMake option CPPSORT_STATIC_TESTS: when ON some tests are turned into static_assert and are reported as success if the program compiles. The option defaults to OFF.
    • New wiki section to document the concept of transparent function objects.
    • Give the [comparison] tag to more tests, unify similar tags.
    • Move every_sorter_* tests from the root of the test suite to the sorters subdirectory.


    Known bugs

    I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.

    Source code(tar.gz)
    Source code(zip)
  • 1.12.1(Dec 16, 2021)


    This release is named after Tristam's timeless glitch hop classic Till It's Over, which is always a favourite of mine when I want to be pumped up while programming — or doing anything else, really.

    This end-of-the year release mostly fixes bugs and warnings, but also delivers a few small improvements to the library and its tooling that were ready and unlikely to cause issues. Notably sorters and adapters should now be able to handle some iterators even when they define a difference_type smaller than int.

    Bug fixes

    • counting_sorter::iterator_category and counting_sorter::is_always_stable were accidentally unavailable since version 1.9.0 unless __cpp_lib_ranges was defined. They are now unconditionally available again.
    • Due to a missing using declaration, slab_sort only compiled for iterators with an ADL-found iter_swap.
    • Fix compile time error in quick_sort when the passed iterators have a difference_type smaller than int.


    • slab_sort now works with bidirectional iterators.
    • drop_merge_sort does not need to compute the size of the collection anymore, which saves a full pass over the collection to sort when with bidirectional iterators.
    • Reduce the number of memory allocations performed by spin_sort.
    • utility::size now also works with collections that only provide non-const begin() and end() functions.
    • Fix warnings in the following sorters due to integer promotion issues when the passed iterators have a difference_type smaller than int:


    • Rollback changes to the patterns benchmark accidentally committed in version 1.12.0.
    • Rewrite large parts of the bubble sort tutorial.
    • Test sorters and adapters with an iterator type for which difference_type = std::int8_t.

    Known bugs

    I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.

    Source code(tar.gz)
    Source code(zip)
  • 1.12.0(Dec 2, 2021)


    To my utmost surprise, my life has recently taken a weird turn where I'm doing more fitness-related activities than I thought I would ever do: muscle-strengthening and stretching on a regular basis, and I even started to play badminton again after a 12-year hiatus. My self from three years ago would probably call me a liar while reading those lines. Life can be weird, eh... Anyway, it's still leaving me enough time to work on cpp-sort and to release new versions.

    One of the main highlights of this release is the improved support for measures of presortedness: one was added, one was deprecated, and several were improved. As a result, all of the library's measures of presortedness run in O(n log n) or better — save for a deprecated O(n²) that will be removed in the future.

    Benchmark speed of measures of presortedness for increasing size for std::vector

    Much effort went into improving the overall library quality: bug fixes, consistency fixes, binary size improvements, better tooling and documentation, etc. One of the biggest items was the switch from GCOV to LCOV as a code coverage engine: it actually reports a correct line coverage while I never managed to get GCOV to show all the lines that were actually covered by the test suite. As a result the library's line coverage is now over 90% and it will now be easier to cover the missing parts.

    One of the smaller features that got some library-wide attention is the handling of stable sorting: several bugs were fixed, and a few parts of the library were changed to ensure that stable_t would do a better job at "unwrapping" stable_adapter. These changes caused a few minor breaking changes, which should however not be issues when the library features are used correctly. The documentation was also updated to better explain the logic behind stable_t and stable_adapter (with graphs) and to clarify the expectations around the related type traits.



    Right invariant metrics and measures of presortedness by V. Estivill-Castro, H. Mannila and D. Wood mentions that:

    In fact, Par(X) = Dis(X), for all X.

    After checking, it appeared that probe::dis and probe::par indeed both returned the same result for the same input. The authors of Par stopped using Par in their subsequent publications and preferred using Dis instead, so we follow suit and deprecate probe::par accordingly since it is redundant with probe::dis. It will be removed in version 2.0.0.

    probe::osc O(n²) fallback

    The measure of presortedness probe::osc was improved to run in O(n log n) time and O(n) space instead of O(n²) time and O(1). The old algorithm is still used as a fallback when there isn't enough memory available - to avoid breaking backward compatibility -, but that fallback is deprecated and will be removed in version 2.0.0.

    The rationale is that we don't want to keep quadratic algorithms around without a good reason. Measures of presortedness are first and foremost (expensive) diagnostic tools, and as such they aren't expected to run on resource-constrained environments. It makes sense to expect extra memory to be available when suing such tools.

    Deprecation warnings can be disabled by defining the preprocessor macro CPPSORT_DISABLE_DEPRECATION_WARNINGS.

    New features

    New measure of presortedness: probe::block: it implements Block(X) — described by S. Carlsson, C. Levcopoulos and O. Petersson in Sublinear Merging and Natural Mergesort —, slightly modified so that to handle equivalent elements correctly and in a way that makes it a correct measure of presortedness according to the formal definition given by Mannila. Block(X) corresponds to the number of elements in X sequence that aren't followed by the same element in the sorted permutation of X. Its worst case returns |X| - 1 when X is sorted in reverse order.

    Bug fixes

    • Not all comparisons in probe::osc were performed with the provided comparator, which could lead to compile-time or runtime errors.
    • Fixed an issue where merge_insertion_sort and slab_sort produced a memory error (caught by Valgrind and address sanitizer) when called on an empty collection (issue #194).
    • stable_adapter<T> did not support construction from T when T was one of the following types (which was not consistent with the other specializations):
    • stable_adapter<default_sorter>::type now aliases stable_adapter<default_sorter> instead of merge_sorter. This is technically a minor breaking change, but stable_adapter<T>::type is supposed to be constructible from T so the new behavior is correct.
    • Since their last rewrite in version 1.9.0, verge_sorter and verge_adapter always used their stable algorithm, even when they weren't wrapped in stable_adapter. That was an accident, and they now use the unstable algorithm by default, as they should have done.


    • probe::dis now runs in O(n log n) time and O(1) space. When sorting bidirectional iterators, if enough heap memory is available, it uses an O(n) time O(n) space algorithm described by T. Altman and Y. Igarashi in Roughly Sorting: Sequential and Parallel Approach.
    • probe::par is now a deprecated alias for probe::dis and thus benefits from the same improvements.
    • probe::osc now runs in O(n log n) time and O(n) space. The old algorithm that ran in O(n²) time and O(1) is still used as a fallback when not enough memory is available, but it is deprecated and will be removed in a future breaking version. Thanks a lot to @Control55 from @The-Studio-Discord for coming up with the algorithm.
    • stable_t<Sorter> now uses Sorter::type when it exists and Sorter is a stable_adapter specialization.
    • stable_adapter<Sorter>::type now does a better unwrapping job when Sorter is itself a stable_adapter specialization.
    • sorter_traits now has a partial specialization for stable_adapter where is_always_stable always aliases std::true_type. It was introduced to defensively enforce this contract on user specializations of stable_adapter.
    • Some work was done to reduce the size of the binary bloat in various places, with additional small gains in C++17. It is mostly noticeable when the same components are instantiated for different types of collections.
    • Reduce recursion in the implementation of quick_merge_sort for forward and bidirectional iterators.



    • The documentation about measures of presortedness was reworked and improved a bit. A new section describes some measures of presortedness that appear in the literature but don't explicitly appear in the library.
    • Improve the documentation for stable_adapter and related feature. Add graphs to visually explain the logic behind them.
    • Rewrite parts of the documentation about sorter_traits and related features. Make some usage expectations clearer.
    • Fix broken links and Markdown errors.

    Test suite:

    • WARNING: several changes affect random number generation in the test suite. As a result, errors encountered when running the test suite with specific seeds prior to this release might not be reproduced with new versions of the test suite.
    • Bump downloaded Catch2 version to v2.13.7.
    • Fix segfaults that occurred when running the memory exhaustion tests with some versions of MinGW-w64.
    • Fix some -Winline warnings with GCC and MinGW-w64.
    • Fix /W2 conversion warnings with MSVC.
    • Test more documented relations between measures of presortedness.
    • Add more tests to improve coverage.
    • The parts of the test suite that used random numbers have been updated to use less memory at runtime.
    • Greatly reduce the number of thread_local pseudo-random engines instantiated by the test suite.

    Code coverage:

    • Use LCOV instead of gcov in the coverage GitHub Action, which seems to better represent what was really executed, and brings the coverage to more than 90%.
    • Bump codecov/codecov-action to v2.
    • Update the embedded CMake-codecov scripts, which notably makes code coverage work with MinGW-w64.
    • Move codecov.yml to .github/.codecov.yml to reduce the number of files at the root of the project.
    • More small tweaks and fixes to the coverage handling in the test suite's CMakeLists.txt and in the GitHub Action.


    • GitHub Actions: bump the Ubuntu version from 16.04 to 18.04.
    • GitHub Actions: fix the Ubuntu job so that it actually shows the Valgrind logs when a Valgrind jobs fails.
    • GitHub Actions: run CTest with --no-tests=error because no tests run by the test suite is always an error.
    • Fix includes in benchmarks to work out-of-the-box.
    • Simplify the example in the README a bit, and add it to the examples directory.

    Known bugs

    I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.

    Source code(tar.gz)
    Source code(zip)
  • 1.11.0(Jul 24, 2021)


    I am writing those release notes in the middle of a heatwave — 32°C, you might laugh but I live in a region where that's unusually high enough for AC and fans to be uncommon around here —, which means that my brain is too confused to think of a better name or of anything else for what it's worth.

    The biggest features in this release are the addition of several tools to create and manipulate sorting networks, including two new fixed-size sorters implementing specific sorting network algorithms. The rest is mostly the usual smaller improvements, bug fixes and all those things that are needed to improve the overall quality of the project.


    block_sort is now deprecated and will fire a deprecation warning if used. It will be removed in cpp-sort 2.0.0. wiki_sort was added to the library to replace it.

    Block sort is not a single sorting algorithm, but a whole family of sorting algorithms that shift blocks to sort a collection. Those algorithms are often in-place stable comparison sorts. cpp-sort provides two such algorithms: WikiSort and grail_sort. However WikiSort used the general name block_sort, which seemed more and more unclear and unfair as years went on, especially when considering that new block sorts have been implemented in the recent years, and more are being worked on.

    Deprecation warnings can be disabled by defining the preprocessor macro CPPSORT_DISABLE_DEPRECATION_WARNINGS.

    New features

    This release adds several new features related to sorting networks. The goals are to start completing the library's collection of fixed-size sorters based on sorting networks, and to provide new user-facing tools that make manipulating and creating sorting networks easier.

    New header <cpp-sort/utility/sorting_network.h>

    This new utility header will contain all generic tools related to sorting networks specifically. It contains the following vocabulary type:

    template<typename IndexType>
    struct index_pair
        IndexType first, second;

    Sorting networks work by performing a fixed sequence of compare-exchange operations on pairs of elements in the collection to sort. index_pair represents the pair of indices used to access the elements on which a compare-exchange operation will be performed. There is an implicit assumption that first < second, but it is never checked by the library. Currently the vocabulary type to represent a sequence of compare-exchange operations is std::array<index_pair<IndexType>, N>.

    This new header also contains the function templates swap_index_pairs and swap_index_pairs_force_unroll, which accept an iterator to the beginning of a random-access collection and an std::array<index_pair<IndexType>, N>. Both functions use the index pairs to perform compare-exchange operations on the collection - effectively applying operations like a comparator network. The former simply loops over the index pairs while the second is a best effort function that tries its best to unroll the loop.


    All sorting_network_sorter specializations got a new index_pairs() static member function with the following signature:

    template<typename DifferenceType=std::ptrdiff_t>
    static constexpr auto index_pairs()
        -> std::array<index_pair<DifferenceType>, /* Number of CEs in the network */>;

    It returns the sequence of compare-exchange operations used by a network to sort its inputs. It builds upon the features introduced in the previous section.

    merge_exchange_network_sorter and odd_even_merge_network_sorter

    Those new fixed-size sorters are sorting networks that implement two variations of Batcher odd-even mergesort, an algorithm that halves the collection to sort, sorts both halves recursively then merges them. The former halves the input by considering that the first half is on the even lanes of the network and the second half on the odd lanes. The latter consider that the first half is on the first N/2 lanes of the network, and the second half is on the last N/2 lanes. Both are pretty similar and interchangeable in most scenarios.

    merge_exchange_network_sorter over 8 inputs odd_even_merge_network_sorter over 8 inputs

    Both provide a static index_pairs() method similar to the one described in the previous section.

    Bug fixes

    • If container_aware_adapter<insertion_sorter> worked at all when sorting an std::forward_list, it was purely accidental prior to this release: that's how bugged it was. Now it should be fixed, and way faster than it used to be when it accidentally worked.
    • Fix a potential bug in cartesian_tree_sorter: when an exception was thrown during the construction of the Cartesian tree, the algorithm would try to destroy elements that had not been constructed yet.
    • Fix potential use-after-move issues in stable_adapter.


    • The conversion to function pointer operators of sorter_facade were improved to allow sorters to be converted to function pointers returning void regardless of the type they're supposed to return. In such a case, any value returned by the sorter is ignored/discarded. This allows to pass some sorters to functions expecting a void-returning function, or to more easily store sorters into arrays as function pointers no matter their return type:
      using sort_t = void(*)(std::vector<int>&);
      sort_t available_sorters[] = {

      Those conversions still don't work with MSVC (see issue #185).

    • container_aware_adapter<insertion_sorter> is now around 50% faster in benchmarks when sorting an std::list. Benchmark the new container_aware_adapter<insertion_sorter> over std::list against the old version
    • probe::enc is now up to 40% faster for small types when the comparison and projection are considered likely branchless. This improvement is thanks to a variation on binary search proposed by @scandum called monobound binary search. Benchmark the new probe::enc over std::vector against the old version
    • cartesian_tree_sort now also works with forward and bidirectional iterators.
    • Fix a warning about [[nodiscard]] when using mel_sort.
    • Fix a warning about a unused typedef which fired when compiling container_aware_adapter<mel_sorter> with Clang.
    • Reduce a bit the memory use of mel_sort (up to sizeof(T) * n/2 less memory is allocated).



    • Add dist::as_long_string function object to turn a long long int into a std::string of 50 characters whose last characters are the digits of the long long int; this allows to use all the existing distributions to create strings. The big sequence of equal characters at the beginning of the strings make the comparisons expensive, which is a benchmarking category that was often overlooked up to now.
    • The visualization part of the patterns benchmark now accepts an --errorbars option to display the standard deviation.
    • Add "lower is better" indications on the relevant axis of the benchmark plots to make them more easily understandable (the graphs in these release notes predate that change, sorry about that).


    • Give a formula to compute the number of compare-exchanges performed by a hypothetical merging network based on repeated half-cleaner networks.

    Test suite:

    • Bump downloaded Catch2 version to v2.13.6.


    • Conan integration: fix test when cross-building in test_package.

    Known bugs

    I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.

    Source code(tar.gz)
    Source code(zip)
  • 1.10.0(Mar 30, 2021)


    Here comes a new release after merely two months, making it the minor version of the library with the shortest development cycle so far. I haven't done anything super interesting recently so that release name is dedicated to all the dreams I've written down since the beginning of the pandemic, mostly adventures, improbably situations and lots of fun — it's nice being able to live adventures in my dreams when every day life is slow. Speaking of fun: it was pretty much the leading force behind this release, which was reified as one new measure of presortedness and three new sorters, mostly implemented after research papers from the 80s and 90s.

    One of the most important (but not fun) changes is that cpp-sort now works with MSVC 2019 (only with /permissive-): the compiler front-end evolved sufficiently to compile most of the library, so I decided to change the library where needed to fully support it — which also allowed to fix small bugs in several parts of the library, improving its overall quality. The only big feature that still doesn't work is the ability to convert a sorter to a variety of function pointers (issue #185).

    New features

    New sorters: one of the goals of this release was to be fun, and what's more fun than implementing unknown algorithms from old research papers without having to care about them being the fastest in the land? This release adds several new sorting algorithms, mostly found in the literature about adaptive sorting from the 80s and 90s. On average those new algorithms are adaptive, but slow and impractical for most real world use. However their inclusion in the library means that they now have an open-source implementation, which is always something valuable.

    • cartesian_tree_sorter: it implements a Cartesian tree sort, an Osc-adaptive comparison sort introduced by C. Levcopoulos and O. Petersson in Heapsort - Adapted for Presorted Files under the name maxtree-sort. The algorithm uses a Cartesian tree and a heap to sort a collection.
    • mel_sorter: it implements melsort, an Enc-adaptive comparison sort described by S. Skiena in Encroaching lists as a measure of presortedness. It works by creating encroaching lists with the elements of the collection to sort then merging them. When used together with container_aware_adapter, mel_sorter provides specific algorithms for std::list and std::forward_list than run in O(sqrt n) extra memory instead of O(n).
    • slab_sorter: it implements slabsort, an SMS-adaptive comparison sort described by C. Levcopoulos and O. Petersson in Sorting Shuffled Monotone Sequences. The algorithm builds upon the adaptiveness of melsort to take advantage of even more existing presortedness in sequences to sort.

    Benchmark slow O(n log n) sorts over different patterns for std::vector

    Measures of presortedness (MOPs): the literature about adaptive sorting is also about MOPs, so those were given some love for the first time in a while:

    • New MOP probe::sus which implements SUS(X) as described by Levcopoulos and Petersson in Sorting Shuffled Monotone Sequences. It computes the minimum number of non-decreasing subsequences (of possibly not adjacent elements) into which X can be partitioned. It happens to correspond to the size of the longest decreasing subsequence of X. Its worst case returns n - 1 when X is sorted in reverse order.
    • MOPs now all have a static max_for_size function which takes a size and returns the maximum value that the MOP can return for the given size. This helps to give a better scale for how much presortedness represents the value returned by a specific MOP.

    More constexpr: this release also brings very basic constexpr support to some of the library's building blocks: sorter_facade, iter_move and iter_swap. None of the library's sorters or sorter adapters have been updated to work in a constexpr context (this would require C++17/C++20 library features, or reinventing the wheel again), but these changes mean that it is possible for a user to write a constexpr-friendly sorter implementation, wrap it with sorter_facade, and get a - mostly - constexpr sorter ("mostly" because the ranges overload require C++17 features to work in a constexpr context). More comprehensive constexpr support is planned for a future 2.0.0 release (see issue #58).

    Bug fixes


    • The conversion from a sorter to a function pointer is now unconditionally constexpr (it used to only be constexpr in C++17 mode and later).
    • Change grail_sort to use difference_type instead of int wherever it matters in its implementation. It solves some conversion warnings, and might even solve potential overflow issues with big collections.
    • Silence several conversion warnings.
    • probe::enc now performs up to 40% fewer comparisons.
    • Reduce the number of allocations performed by merge_insertion_sorter. This doesn't affect its speed nor its memory complexity.



    • The distributions are now constructed with a long long int instead of a size_t.
    • Change the default patterns in the patterns benchmark.


    • Complete the introduction about MOPs, add a graph showing the partial ordering for MOPs.
    • Remove mentions of Bintray.

    Test suite:

    • Test that all sorters handle projections returning an rvalue.
    • Add minimal to check that sorters behave correctly when a move operation throws.
    • Test that all MOPs return 0 when given a collection of equivalent values.
    • Test more relations between MOPs described in the literature.
    • Remove alternating_16_values tests, they never gave results significantly different from shuffled_16_values.
    • The distributions are now constructed with a long long int instead of a size_t.
    • The whole test suite was successfully compiled and executed with -no-rtti.


    • Add MSVC 2019 builds to the continuous integration.
    • The minimal supported Conan version is now 1.32.0.
    • The configuration checks in were moved from configure() to validate().
    • No more @morwenn/stable packages on Bintray: JFrog is sunsetting Bintray. Only the Conan Center packages will be updated from now on.
    • Tweak tools/test_failing_sorter.cpp to make it more useful.

    Known bugs

    I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.

    Source code(tar.gz)
    Source code(zip)
  • 1.9.0(Jan 30, 2021)


    I kind of managed to turn the current pandemic, lockdowns and even general stay-at-home endeavours without an explicit lockdown into opportunities to work on several side projects — this is already the third cpp-sort release whose name is directly inspired by those side projects, which somehow means a lot. A windbelt is a small device used to harvest wind energy and turn it into electricity, generally a rather cheap DIY project since the required components can often be found around the house. I just finished mine, and even though I still need to test it it's as good as anything for a release name.

    This release continues to pave the road to the future breaking 2.0.0 version of the library, even though it always seems to draw further away — there will definitely be more 1.x.y versions. As a result this release brings a few deprecations, polishing of existing features, and initial support for some C++20 features. One of the big items was also the move of the whole continuous integration from Travis CI to GitHub Actions.


    All of the following CMake configuration variables and options are deprecated:


    Equivalent options prefixed with CPPSORT_ have been added to replace them. For backwards compatibility reasons, the new options default to the values of the equivalent deprecated variables.

    New features

    Some limited C++20 support was added to the library:

    • When available, std::identity can be used wherever utility::identity can be used, including in the places where the latter is used as a "joker". In the future 2.0.0 version of the library, std::identity will entirely replace utility::identity (issue #130).
    • When available, std::ranges::less and std::ranges::greater can be used wherever std::less<> and std::greater<> can be used, including in the places where the latter is used as a "joker". In the future 2.0.0 version of the library, std::less<> and std::greater<> will remain the main vocabulary types because they are less constrained that their new counterparts (issue #130).

    Other new features:

    • stable_adapter and its specializations might define a member type named type: this type should be an alias to the "least nested" sorter with the same behaviour as the stable_adapter specialization which is guaranteed to always be stable - it can be the stable_adapter specialization itself.
    • A new stable_t alias template is available when including <cpp-sort/adapters/stable_adapter.h>. This alias takes a sorter template parameter and aliases a possibly adapted sorter which is always stable. It is meant to replace stable_adapter when the goal is to take any sorter and to get a stable sorter (stable_adapter remains the customization point). One of the goals is to reduce template nesting when possible, with the hope that it leads to better diagnostics and smaller template stack traces. For a given sorter Sorter, stable_t<Sorter> will follow these rules:
      • If cppsort::is_always_stable_v<Sorter> is true, then stable_t aliases Sorter.
      • Otherwise if stable_adapter<Sorter>::type exists, then stable_t aliases it.
      • Otherwise stable_t aliases stable_adapter<Sorter>.
    • A new comparator projection_compare can be used to embed both a comparison and a projection into a single comparison object, allowing to easily use projections with algorithms that don't support them explicitly:
      // Sort a family from older to younger member
      std::vector<Person> family = { /* ... */ };
      std::sort(family.begin(), family.end(), cppsort::make_projection_compare(std::greater<>{}, &Person::age));
    • A new CPPSORT_ENABLE_AUDITS macro can be defined to enable library audits. These audits are assertions too expensive to enable with CPPSORT_ENABLE_ASSERTS: some of them might even change the complexity of the algorithms performing the checks.

    Bug fixes

    • Fix ska_sorter for signed 128-bit integers when both positive and negative values are present in the collection to sort.
    • The random-access version of quick_merge_sorter was O(n²) because it relied on libc++'s implementation of std::nth_element which is itself O(n²). It was replaced with miniselect's implementation of Andrei Alexandrescu's QuickselectAdaptive algorithm, ensuring that quick_merge_sort is O(n log n) as documented (issue #179). Comparisons performed against a quicksort killer pattern, showing the O(n²) behaviour of the old random-access version of quick_merge_sort
    • Fix a potential move-after-free bug in pdq_sorter, affecting all components that rely on it.


    • The bidirectional overload of verge_sorter was significantly reworked in order to make the optimized path faster, while keeping its previous speed for the path where the vergesort layer doesn't find big enough runs. The improvements are especially noticeable for the Ascending sawtooth and Descending sawtooth in the patterns benchmark. Here is a brief summary of the main improvements:
      • It now uses the same k-way merge algorithm as the random-access overload. Among other things this means that the bidirectional overload should now have the complexity described in the documentation. I am still unsure whether it was the case before or not.
      • It is now smarter about which element should belong to which run, and as a result generates fewer 1-element runs, which leads to fewer merges overall.
      • It now spends less time computing std::distance prior to merges. Old vs. new unstable verge_sorter benchmark over std::list
    • stable_adapter now has dedicated specializations for verge_sorter and verge_adapter instead of relying on make_stable. The stable algorithm is a bit different from the unstable one: it detects strictly descending runs in the collection to sort instead of non-ascending ones, and wraps the fallback sorter in stable_t. This addresses issue Morwenn/vergesort#11 in the standalone project, and gives a partial answer for issue Morwenn/vergesort#7. Old vs. new stable verge_sorter and verge_sorter benchmarks over std::deque Old vs. new stable verge_sorter benchmark over std::list The benchmarks above clearly show the difference for the fast vergesort path for random-access iterators. The significant decrease in speed in the bidirectional benchmarks is due to the fact that stable_adapter<verge_sorter> used make_stable in 1.8.1, which actually creates a buffer of N elements and performs a random-access sort there. As a result the new version uses less memory but is slower. It is still possible to get the 1.8.1 behaviour using make_stable<verge_sorter>.
    • Nested stable_adapter now unwraps. It is a scenario that could happened from time to time, and should produce clearer error messages thanks to the reduced nesting.
    • utility::is_probably_branchless_comparisons and utility::is_probably_branchless_projection now have specializations for more comparisons and projections (#177), both for internal and standard library types. These changes mean that pdq_sorter uses its branchless partitioning algorithm in more scenari (which tends to be faster on average, but slower for some patterns). Since many components rely on pdqsort, the changes should be noticeable throughout the library. The changes affect the following features:
      • The type returned by std::mem_fn in libc++ and libstdc++ is now considered likely to be branchless when it wraps a pointer to data member. utility::as_function uses std::mem_fn to make pointer to members callable, so this change might have repercussions in most of the library.
      • The C++20 function object std::identity is always considered branchless.
      • The C++20 function objects std::ranges::less and std::ranges::greater follow the same rules as std::less<> and std::greater<> when determining whether they are considered branchless.
      • ska_sorter and schwartz_adapter have been enhanced to more often pass comparison of projection functions considered likely branchless to their underlying algorithms.
      • The comparison adapter used by counting_adapter is now considered likely branchless when the adapted comparison is likely branchless itself, and when the type used for counting is a built-in arithmetic type. Old vs. new counting_adapter(pdq_sorter) benchmark over std::vector



    • Fix a MatplotlibDeprecationWarning in the errorbar-plot benchmark.


    • Change the documentation here and there to make it more forward-compatible with the changes coming in 2.0.0.
    • Change HTTP links to HTTPS when possible.
    • Fix some incorrect uses of cppsort::sort that still used the pre-1.0.0 parameters order.
    • More small fixes to improve the overall quality of the documentation.

    Test suite:

    • Some files testing cppsort::sort and cppsort::stable_sort were in the sources but never run as part of the test suite. They are now correctly run.
    • Tests sorters with a new median_of_3_killer distribution, which implements a pattern known to be adverse to common quicksort implementations, making them go quadratic (#178). This distribution was implemented after the paper A Killer Adversary for Quicksort by M. D. McIlroy.
    • Improve stable_adapter tests thanks to a new descending_plateau distribution.
    • Bump the downloaded Catch2 version to v2.13.4.
    • General maintenance and cleanup of the existing tests.

    Continuous integration:

    • The continuous integration was fully moved from Travis CI to GitHub Actions (#176), with a number of changes in configurations coverage, see below.
    • The oldest tested Clang release is now Clang 6 instead of Clang 3.8. The latter probably still works but there are no automated tests for it anymore.
    • There are now tests for g++ on MacOS.
    • There are now tests with AddressSanitizer and UndefinedBehaviorSanitizer on MacOS.
    • There are no tests with Valgrind's memcheck tool on MacOS anymore.
    • The overall number of compiler versions tested should be greater, because the different OS have different minimal compiler versions available.


    • Some CMake options were deprecated and replacements introduced. See the Deprecations section of these notes.
    • The project's .gitignore now only ignores the files that can be generated with the library tooling.
    • Tweaks to the tool used to debug sorters to make it more usable.

    Known bugs

    I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.

    Source code(tar.gz)
    Source code(zip)
  • 1.8.1(Oct 25, 2020)


    It's spooky month in Pokémon Go, and as a result I've found myself listening to several remixes of the Lavender Town theme - an all-time favourite of mine - while preparing this release. Consider it project culture now that bugfix releases are named after songs since I can't wait for something specific to happen to me to name those (which is something I tend to do with other releases).

    The release itself is mostly a number of bug fixes, documentation fixes and tiny improvements. Most of those were the result on working on several smaller sorting-related projects that share some code with cpp-sort.

    Bug fixes


    • Fix the implementation of the Tukey's ninther used for pivot selection by quick_sorter and quick_merge_sorter. A bug in the elements being swapped meant that a value further away from the median was picked sometimes. It is unknown whether this was sufficient to change the complexity of the algorithm, but no significant difference in speed was noticed after the change.
    • The bidirectional iterators version of verge_sorter now returns early if the collection is already sorted.
    • poplar_sorter was tweaked to ensure that it only ever performs a single memory allocation to track the poplars.


    • Specifically download Catch2 v2.13.2 when no suitable version of Catch2 is found on the system. This is technically a bugfix since the master tag was use so far for the download, and it was recently removed from the repository.
    • The now raises a ConanInvalidConfiguration error when the target compiler does not support C++14.
    • Update the original research page of the wiki with up-to-date information.
    • Add a checklist of tasks to perform when releasing a new version of the library. This should prevent some issues that commonly occur while preparing a release.
    • Change the Conan badge in the README to point to the new Conan Center website.

    Known bugs

    I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.

    Source code(tar.gz)
    Source code(zip)
  • 1.8.0(Sep 27, 2020)


    I have started cooking a bit more during the confinement, and I've recently made a bunch of mochis, which were some of the delicacies I missed the most from the trip in Japan. I've also cooked some Japanese curry and increasingly improved instant noodles, but mochis were more of a symbol. My taste buds are satisfied, it's time for a new cpp-sort release.

    This release brings no new feature, but improves the existing ones a lot, and deprecates a few. Special care was given to the algorithms that support forward and bidirectional iterators, many of whom were a bit neglected or suffered from excessive pessimization. The other big things in this release are the improvements in tooling. You can read more about it below, but here is the gist of it:

    • The wiki pages are now in the main source repository, and a GitHub Action automatically updates the wiki when a new release is created.
    • New benchmarks were added to display interesting properties of some algorithms.
    • The Benchmarks page of the documentation was totally rewritten, and all benchmarks were regenerated to be up-to-date with the library.


    The following features are now deprecated and will fire deprecation warnings if used. They will be removed in cpp-sort 2.0.0 (see the linked issues for the rationale for deprecation & removal):

    Deprecation warnings can be disabled by defining the preprocessor macro CPPSORT_DISABLE_DEPRECATION_WARNINGS.

    Bug fixes

    • Add missing includes to out_of_place_adapter that sometimes triggered compile time errors.
    • The declared iterator_category of out_of_place_adapter is now always std::forward_iterator_tag, in line with what the documentation claimed.
    • Fix bug that sometimes occurred when sorter_facade was used to add projections support to an algorithm that only handles comparisons. This might fix issues with std_sorter.
    • Fix bugs due to use of moved-from comparison and projection functions in probe::exc, probe::ham and probe::max.
    • Fix construction of stable_adapter<std_sorter> from an instance of std_sorter. It mainly makes it more usable with C++17 implicit deduction guides.


    • indirect_adapter now also works with forward and bidirectional iterators (#166). The algorithm underlying these new capabilities is Matthew Bentley's indiesort. The resulting sorter can sort any iterator category regardless of the iterator category of the adapted sorter.
    • When given forward iterators and when no extra heap memory is available, merge_sort is now globally faster than it used to (see the story here if you want fun trivia): Old vs. new merge_sort benchmark
    • When given forward iterators or bidirectional iterators, probe::dis is now O(n²) instead of accidentally being O(n³), leading to ridiculously huge improvements: Old vs. new probe::dis for std::forward_list The algorithm was further improved with a heuristic allowing it to short-circuit non-negligible parts of the computation when it doesn't hit one of the worst cases: New vs. newer probe::dis for std::list In the graph above probe::dis-dev corresponds to probe::dis in the previous graph - the color was kept for consistency. It is also worth nothing that the collection used is 10 times the size of the one used for the previous graph.
    • Other sorters, adapters, measures of presortedness and internal algorithms that handle forward and/or bidirectional iterators used to start by computing the size of the passed collection, which was often rather sub-optimal (#169). Those components were reviewed prior to this release, and changed as needed. They now perform O(n) fewer operations when passed a collection which provides its size in O(1), leading to speed improvements in the following user-facing function objects:
    • The sorting network for 18 inputs uses fewer compare-exchange units than it used to thanks to the latest results of SorterHunter.
    • The sorting networks for 21 and 22 inputs also use newer results from SorterHunter. These networks don't have a smaller size than before, but have a smaller depth.
    • The removal of cppsort::sort led to the change of the few parts of the library that relied on it. These lead to simpler error messages in those places.
    • verge_adapter had static assertions to ensure that the algorithm only handled forward iterators instead of bidirectional ones. This wasn't buggy per se but led to useless static assertions, and less clear error messages.



    • New benchmark to compare the evolution of the running times of different sorting algorithms when the size of the collection grows. New error bar plot benchmark over all probes
    • New benchmark to visualize how the speed of some algorithms evolve with the number of inversions in the collection to sort. New inversions benchmark over Inv-adaptive algorithms
    • Some of the benchmarks now use a colorblind-friendly palette created by Thøger Rivera-Thorsen (unfortunately not the one above since it uses more colors than the new palette).
    • The benchmarks directory was reorganized and now has one subdirectory per benchmark.
    • patterns and small-array benchmarks now ensure that every sorter will be given the same input for random distributions, making the generated graphs more relevant.
    • patterns now takes the root of the results directory as a command-line parameter instead of forcing it to profiles.
    • patterns and errorbar-plot have an --alternative-palette option to switch to an infinite colour palette instead of the new default colourblind-friendly palette.
    • small-array was enhanced with the experience gathered from the other benchmarks.
    • Benchmarks now log the seed they were initialized with for better reproducibility.
    • The benchmark distributions can now be passed a projection function to transform the generated size_t into any type in a custom way.


    • The documentation sources are now in the main GitHub repository (#157), and a GitHub Action updates the wiki whenever something is pushed to master. This change makes things better in several ways:
      • Code, tests and documentation can be committed at the same time, increasing the coupling and making it easier to track or revert related changes.
      • It makes it easier for non-maintainers to contribute to the documentation.
      • It is now possible to have a specific version of the library with a matching documentation.
      • The day we switch to version 2.0.0, it will be possible to cleanup the documentation and having the doc for version 1.x and 2.x live side by side in different branches.
      • The documentation is now easily browsable for a given release or branch.
    • The Benchmarks page was completely regenerated, updated with new benchmarks and reorganized. I hope that I will be able to keep it updated in the future.

    Test suite:

    • Additional tests for adapters that can handle forward iterators and/or bidirectional iterators.
    • Test some measures of presortedness when no heap memory is available.
    • Additional tests to ensure that sorters and measures of presortedness don't use a moved-from comparison or projection.


    • New tool which renames all references to cpp-sort in the library, mainly used to test different versions of the library's algorithms side-by-side in benchmarks.
    • All source files now use an UTF-8 encoding.
    • The handling of licenses changed a bit: the way all the files are licensed now appears in a clearer way, there is NOTICE.txt file describing all the extra licenses, most files without an explicit license were changed to display one. Also source files now use a short form of the copyright notice in order to reduce the redundant per-file information.

    Known bugs

    I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.

    Source code(tar.gz)
    Source code(zip)
  • 1.7.0(Jun 24, 2020)


    I spent a great deal of time during the recent confinement identifying flowers and other plants in my garden, and I also learnt to cook some of them. I was left with a a few hundred plant pictures on my phone and decided to start a tiny glitch art side project with some of the flower photos. With all those flowery endeavours behind me, it was time to come back with a fresh cpp-sort release.

    New features

    Chainable projections through operator| have been implemented (issue #82), allowing to apply several transformations in a row when projecting a collection's element:

    struct wrapper { int value; };
    std::vector<wrapper> vec = { /* ... */ };
    auto&& negate = cppsort::utility::as_projection(std::negate<>{});
    // Applies &wrapper::value to the elements of vec, then negate
    cppsort::split_sort(vec, &wrapper::value | negate);

    The new operator| only considers classes inheriting from cppsort::utility::projection_base during overload resolutions. In order to make your own projections work with you can either make them inherit from projection_base, or adapt them with cppsort::utility::as_projection.


    • The speed of merge_insertion_sort has been improved (it remains an extremely slow algorithm): The old implementation used std::list internally, with either std::allocator or __gnu_cxx::bitmap_allocator when available to improve the allocation speed. The new implementation uses a custom list data structure which performs a single allocation of all the nodes required by the algorithm.
    • Sorters and adapters now accept comparison functions that take their arguments by non-const reference, it is the responsibility of the caller to make sure that such predicates don't modify their parameters in a way that would affect the consistency of the sort (issue #136). Following the resolution of standard issue LWG3031 it is also the responsibility of the caller to ensure that, should the predicate accept both const and non-const parameters, the results are consistent between overloads.
    • as_comparison and as_projection can now adapt any Callable, and not just objects callable with the normal function call syntax.
    • Fixed an integer conversion warning in pdq_sort (merged a fix from upstream).
    • Fixed a signed/unsigned warning in the measures of presortedness tests.
    • Some compile time error stack traces might point directly into the cpp-sort algorithms instead of in standard library utilities, making them a bit shallower.
    • Reduce the binary size of the code generated by ska_sort a bit.


    • CMake: Catch2 is now looked with find_package first, and only downloaded if no suitable version was found on the system. This notably allows to build the test suite while offline.
    • CMake: Catch2 is not required anymore to build the examples.
    • Fix the so that it works with the most recent Conan versions.
    • Small improvements to in the benchmarking tools.

    Known bugs

    I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.

    Source code(tar.gz)
    Source code(zip)
  • 1.6.0(Feb 2, 2020)


    I didn't have the opportunity to brunch properly since my trip to Scotland back in August where I could enjoy tasty local breakfasts at unreasonable hours - with today's excellent vegetarian brunch that cycle is complete and I can publish a new cpp-sort release.

    New features

    A new spin_sorter has been added to the library, based on the algorithm from Boost.Sort. Spinsort is a stable mergesort derivative which is often faster than the other available stable sorting algorithms. It is a stable comparison sorting algorithm that runs in O(n log n) and requires O(n) additional memory; unlike other algorithms in the library it doesn't have a fallback when there isn't enough extra memory available to merge runs.

    As can be seen in the benchmark result above (sorting a std::vector<long double> with 10^7 elements) it tends to be the fastest of the stable sorts for random data, and is otherwise adaptive when some presortedness exists in the data to sort.

    Bug fixes

    • Fixed a long-standing out-of-bounds issue in tim_sorter, which sometimes triggered Valgrind diagnostics when trying to sort an std::deque (issue #89).
    • Fixed an ODR issue in hybrid_adapter that triggered a compile-time issue with Clang 9 (issue #158).
    • Fixed an unsigned integer overflow in poplar_sorter that triggered a diagnostic with the undefined behaviour sanitizer.
    • Fixed a static_assert that wasn't strict enough in verge_adapter.


    • The library doesn't have naked assert anymore: you now need to define the preprocessor flag CPPSORT_ENABLE_ASSERTIONS explicitly in order to enable assertions. This flag still honours the NDEBUG macro.
    • When verge_sorter is used to sort bidirectional iterators, it now falls back to quick_merge_sorter instead of quick_sorter to sort sections of the data to sort where runs aren't big enough. This lowers the complexity from O(n²) to O(n log n log log n) with a worst case of O(log n log n) space - the complexity's worst case shifts from the fallback to the vergesort layer itself. The vergesort layer still uses O(n) memory when it finds patterns to optimize.
    • counting_sorter is now able to sort collections of [un]signed __int128, even when the standard library is not properly instrumented to support them.
    • Algorithms relying on uninitialized_move may be faster when sorting trivial types. Affected sorters: block_sorter, merge_insertion_sorter, merge_sorter, spin_sorter, tim_sorter and verge_sorter.
    • Fewer copies of comparison and projection functions are performed when using stateful sorters.


    There has been some overarching CMake and Conan cleanups for this release: cpp-sort is notably available on Conan Center now, and the built-in Conan support has been reduced and should only be used by people willing to package their own version of the library.

    • cpp-sort can now be used as a CMake subproject with add_subdirectory without triggering errors.
    • New CMake option BUILD_EXAMPLES (OFF by default).
    • CMake: fixed flags in Debug builds.
    • Examples are now built during CI to avoid breaking them and forgetting about them.
    • The wiki now has a section dedicated to tooling, which currently contains some information about the CMake and Conan integration of the library (issue #153).
    • Improved test coverage for sorters that can handle forward and bidirectional iterators.
    • Added tests to ensure that the library's algorithms marked as such can work even when no heap memory is available.
    • Added tests for algorithms that special cases to handle int128.
    • The releases should now be archived on Zenodo to make them easily citeable.

    Known bugs

    I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.

    Source code(tar.gz)
    Source code(zip)
  • 1.5.1(Aug 18, 2019)

    Tiny Little Pieces: it's both what was broken in the 1.5.0 release and the name of an excellent track by Hypnagog that I often listen to while programming.

    Bug fixes

    • Fix the constructor of hybrid_adapter, which failed for a variety of use cases, and notably when using CTAD in C++17. It now works as expected.


    • The constructor of hybrid_adapter taking sorters is now constexpr.
    • All the overloads of adapter_storage::get() are now constexpr.

    Known bugs

    I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.

    Source code(tar.gz)
    Source code(zip)
  • 1.5.0(Aug 17, 2019)

    I spent the last two weeks enjoying a roadtrip through Scotland, watching the beautiful landscape while two good friends enjoyed driving the van on single-track roads. This feels pretty consistent with the previous Tartan release, and once again it gave me a boost of motivation to publish a cpp-sort release, so here we are.

    New features

    The highlight of this release is the ability for sorter adapters to accept stateful sorters: this is the first step required for supporting mutable sorters in the library (issue #104). This is useful to provide first-class support for sorters that are parametrized at construction time: for example imagine a counting_sorter taking min and max parameters at construction time to avoid having to look them up, it would still be possible to adapt such a sorter as follows:

    auto sort1 = counting_sorter(0, 100); // NOT the cpp-sort sorter
    auto sort2 = cppsort::out_of_place_adapter(sort1);

    Several part of the library have been modified in order to support this feature. Here is an incomplete list of things that changed as a result:

    • Most of the library's sorter adapters can now adapt stateful sorters out-of-the-box. One notable exception is small_array_adapter for which I was unable to come up with a satisfying design.
    • Said sorter adapters now have a get() member function to retrieve a copy of the original sorter, except hybrid_adapter for which a single get() function wouldn't make sense since it adapts several sorters.
    • These sorter adapters now also work with sorters that aren't default-constructible.
    • sorter_facade was updated to handle stateful sorters: it can now be constructed with parameters which are forwarded to the sorter implementation, and it now only provides operators to convert the sorter to different of function pointers when said sorter is empty and default-constructible.

    In order to work properly with sorter adapters, sorters are expected to be copy-constructible: adapters make a copy of the sorters they adapt. Additionally a sorter is expected to be empty and default-constructible for conversions to function pointers to work.

    Under the hood, pretty much every single-sorter adapter inherits from the newly introduced utility::adapter_storage<Sorter> to store and retrieve the sorter they adapt. This class template implements three operations:

    • Construction from a sorter: unless the passed sorter is empty and default-constructible, it copies the passed sorter into its internals.
    • Retrieval of a sorter: if the sorter type it adapts is empty and default-constructible, then it returns a default-constructed instance of said sorter type, otherwise it returns a properly reference to the stored sorter whose const and reference qualifications depend on that of the adapter_storage instance.
    • Invocation of the wrapped sorter: adapter_storage::operator() forwards its parameters to the corresponding operator in the wrapped sorter (or to a default-constructed sorter) and returns the result of that operation.

    If you need to write a sorter adapter that properly handles stateful sorters, then inheriting from adapter_storage is probably the simplest solution to correctly provide the full gamut of semantics described above.

    Bug fixes

    • grail_sorter and tim_sorter now support comparison and projection function objects that aren't default-constructible.
    • Fix codegen issue with MinGW-w64 GCC 9.1, which sometimes triggered a segfault when using quick_merge_sorter (issue #151).


    Function objects from the comparators module have been improved in the following ways (issue #150):

    • The non-refined comparators are now transparent comparators: they have an is_transparent member type which allows them to be used in the standard library's ordered associative containers to compare heterogeneous types.
    • The module now exposes explicit names for the main comparator types: total_less_t, total_greater_t, natural_less_t, etc. to make them more usable where type names are needed.
    • natural_less is now able to compare heterogeneous types as long as they provide begin and end functions returning iterators that share a common value_type.

    Other library improvements:

    • Several out-of-place merge functions used in the library have been improved, which could make the following tools slightly faster: block_sorter, grail_sorter, merge_sorter, split_sorter, verge_sorter and verge_adapter.
    • The internal move[_backward] algorithms have been rewritten to fallback to their std:: counterparts in more situations, which might make a good number of the library's algorithms faster when the std:: algorithms are optimized for specific iterators: this should notably be the case for libc++ std::deque iterators.
    • Further small optimizations for grail_sorter and tim_sorter.
    • If the global operator delete supports sized deallocation, then several allocating algorithms will take advantage of it.


    • The recipe is better integrated with CMake, and notably uses the project's CMakeLists.txt install rules to package the library.
    • The generated CMake package version file is now architecture-independent.
    • The sanitizers should now fail fast when expected to.
    • The Windows builds now correctly work with incremental compilation in Travis.

    Known bugs

    I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.

    Source code(tar.gz)
    Source code(zip)
  • 1.4.0(Apr 9, 2019)

    It was Tartan Day a few days ago, the perfect occasion to wear your kilt or anything tartan. Combined with a surprise carbonade flamande with a friend over the weekend, I had all the energy required to finally fix a remaining bug and push a new cpp-sort release.

    This release brings a single new feature, split_sorter that we will describe later, and a bunch of bug fixes, tiny library improvements, and tooling improvements. The development was somewhat painful because benchmarking split_sort lead me to an existing bug in drop_merge_sort, so I analyzed it, fixed it, wrote a more general test and found bugs in other sorting algorithms, then in measures of presortedness, and even in tooling while I was doing further testing... The rabbit hole went ever deeper, but it eventually came to an end and I could finally produce that single-feature release.

    New features

    A split_sorter has been added to the library, implementing the "in-place" variant of the SplitSort algorithm described in Splitsort—an adaptive sorting algorithm by Levcopoulos and Petersson. split_sort is a comparison-based unstable sorting algorithm that might require O(n) extra memory to speed up an internal merge step, but works fine with O(1) extra memory nonetheless.

    The algorithm is close from drop-merge sort: it computes an approximation of a longest non-decreasing subsequence, excludes the elements that are not part of it, sorts them (currently with pdqsort), and merges the two sequences. The graph below shows how it performs compared to drop-merge sort when sorting a collection with an increasing number of elements not in their place:

    While it shares many similarities with drop-merge sort, they still have a few differences:

    • SplitSort 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. Drop-merge sort on the other hand won't work with O(1) extra memory.
    • The results above show 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.

    split_sort offers a tool similar to drop_merge_sort, but with different tradeoffs.

    Bug fixes

    • The measures of presortedness exc, ham and max now correctly handle duplicate values (#143).
    • Fixed issues due to self-move in the following algorithms (#141): block_sort and drop_merge_sort.
    • Fixed sorting of non-SSO-optimized std::string with the following algorithms (#142): block_sort, drop_merge_sort and grail_sort.


    • Nested hybrid_adapter now automatically unwraps (thanks to @notfoundry for this!). To understand why this feature is interesting, consider the following sorter:

      using sorter = cppsort::hybrid_adapter<

      When called on forward or bidirectional iterators, sorter will use the appropriate sorter. However, without the unwrapping, sorter can never call random_access_sorter because the outer sorter considers the iterator category of the inner sorter, which in this case is std::forward_iterator_tag. With the new unwrapping ability, the sorter above should be equivalent to the following one:

      using sorter = cppsort::hybrid_adapter<

      Therefore it will call random_access_sorter as expected when passed random-access iterators.

    • Avoid Clang -Wc++1z-extensions warnings when using [[fallthrough]] while not in C++17.

    • Small optimizations in block_sort, drop_merge_sort, grail_sort, schwartz_adapter and tim_sort.

    • schwartz_adapter now simply calls the adapted sorter when passed identity as a projection.


    Some efforts were made to improve the build times, notably because of the increasingly high build times of the continuous integration:

    • Use mtime_cache on the CI server to finally have proper incremental builds.
    • When building on Linux with Clang, the testsuite now uses LLD for linking.
    • Only download relevant packages needed for each build in Travis.

    Other tooling changes:

    • The testsuite is now tested on Windows with a 64-bit MinGW-w64 on the CI server.
    • The testsuite doesn't use cotire anymore since it didn't seem to make a difference in build times.
    • We now define proper flags for warnings depending on the compiler when building the testsuite.
    • More tests to cover more potential issues.
    • Fix several issues with the CI reporting failing tests as passing (most notably with ubsan and Valgrind).
    • Ship a suppression file to avoid Valgrind false positives with OSX on the CI server.
    • Add a small tool - test_failing_sorter.cpp - which I often use and tweak to investigate failing sorters.

    Known bugs

    I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs. I still don't have a great version hygiene for those, but I promise that it will improve with the time.

    Source code(tar.gz)
    Source code(zip)
  • 1.3.0(Dec 4, 2018)

    I legit had the best cuddles in my life over the weekend (it's never too late to learn new things apparently), so I am now in a good mood to finish a cpp-sort release ^^ This new release doesn't offer new features on the library side, but the CMake scripts have been totally overhauled to take advantage of modern CMake features and provide a cleaner interface.

    New features

    Overhaul of the CMake scripts:

    • Switch to use the target system instead of of the old directory system.
    • cpp-sort now exports a CMake target.
    • Catch2 is now downloaded at configure time instead of build time, which allows to properly link to the Catch2::Catch2 CMake target. This uses the CMake script Crascit/DownloadProject.
    • Use catch_discover_test to have one CTest test per Catch2 test instead of one CTest test for the whole testsuite.
    • Run CTest tests in parallel now that there are many.
    • Use CTest built-in features to run Valgrind.

    Bug fixes

    • Fix fixed_buffer<0> which miscompiled with Clang 6.
    • probe::mono didn't work when the comparison function was a special kind of callable (e.g. a pointer to member).
    • out_of_place_adapter sometimes didn't work because we accidentally let ADL find a function in an inner namespace instead of fully qualifying it (which was enough for the testsuite).


    • The sorting networks for 23, 24, 25 and 26 inputs use fewer compare-exchange units than they used to thanks to the latest results of SorterHunter.
    • schwartz_adapter now returns the result of the adapted sorter if any when called (#134).
    • indirect_adapter and out_of_place_adapter now return the result of their adapted sorter if any when called (C++17 only, depends on the feature test macro __cpp_lib_uncaught_exceptions) (#134).
    • indirect_adapter now works with projection-only sorters too (e.g. ska_sorter, spread_sorter) (#138).
    • Make the internal algorithms lower_bound and upper_bound somewhat faster, helping to make many algorithms using them slightly faster.


    • The tool to validate sorting networks has been parallelized and now runs a few times faster.

    • Use the CMake script cotire to hopefully improve the build times.

    • Use Catch2's new TEMPLATE_TEST_CASE to significantly reduce the size of the code of the testsuite.

    Source code(tar.gz)
    Source code(zip)
  • 1.2.0(Jul 13, 2018)

    I've recently got my freckles-ridden skin checked for melanomas and I apparently don't have any, which is an excellent occasion to celebrate with a new cpp-sort release. This release brings new tools and several performance improvements to the library.

    New features

    • New sorter: quick_merge_sort. It is a specific flavour of the QuickMergeSort algorithm proposed by Stefan Edelkamp and Armin Weiß with a specific quirk: it starts by partitioning the collection with an equivalent of std::nth_element at its two thirds, then uses an internal mergesort to sort the first two thirds, using the last part of the collection as a swap buffer, then proceeds to sort the last third with the same technique. This sorter runs in O(n log n) even with forward iterators, using at most O(log²n) stack memory due to recursion.
    • New sorter adapter: out_of_place_adapter. This adapter simply moves the elements of the collection to sort to a temporary buffer, sorts the buffer with the adapted sorter, then moves the sorted result back to the original collection. As long as enough memory is available, it is the easiest way to sort a collection providing forward or directional iterators fast enough, allowing to use random-access sorters to sort them in the temporary buffer.

    Bug fixes

    • Apply spreadsort bug fix from boostorg/sort#26


    • quick_sorter is now guaranteed to run in O(n log n) instead of O(n²). In order to achieve this it uses the median-of-medians algorithm to select its pivot when the recursion exceeds 2log n. This brings the space complexity up to O(log²n) due to the stack space used by the mutual recursion of the median-of-medians algorithm.
    • sorting_network_sorter now needs 100 comparisons instead of 101 to sort 21 inputs thanks to the latest results of SorterHunter.
    • When there isn't enough memory available, the random-access overload of the inplace_merge function used by several sorters now uses the Symmerge algorithm described by Pok-Son Kim and Arne Kutzner in Stable Minimum Storage Merging by Symmetric Comparisons instead of the old Dudziński and Dydek algorithm.
    • tim_sorter now reuses a same merge buffer — making it grow as needed — instead of reallocating and deallocating a new buffer whenever it needs to merge runs.
    • ska_sorter is now able to sort collections of [un]signed __int128, even when the standard library is not properly instrumented to support them.
    • stable_adapter<hybrid_adapter<Sorters...>> is now equivalent to hybrid_adapter<stable_adapter<Sorters>...> in order to better take advantage of sorters and adapters specialized for stable_adapter.
    • The library is now C++20 compatible: the library parts removed in C++20 have been replaced by hand-rolled ones.
    • Several small changes to reduce template instantiations in different places.


    • Make it easier to change the type of elements to sort in bench.cpp.

    • The tool to validate sorting networks is a bit faster thanks to a new permutation algorithm based on Gray codes.

    Source code(tar.gz)
    Source code(zip)
  • 1.1.1(Mar 29, 2018)

    I will be away in Japan for a few weeks, which means that it is probably a good time for a bugfix release. No new exciting feature in this release, but several small improvements here and there.

    Bug fixes

    • Work around a Clang bug to fix the implicit deduction guide of counting_adapter in C++17
    • Add missing constructor to stable_adapter<self_sort_adapter> to make implicit deduction guides work in C++17
    • Fix warning about class/struct difference between declaration and definition of hybrid_adapter

    Tiny improvements

    • Make the constructors of sorter adapters taking one or more sorters explicit

    • probe::rem now performs a single pass over the sequence even when passed non-random-access iterators, which might make it slightly more performant in this case

    • Code using std::result_of now uses std::invoke_result when available, making it more robust against type system subtleties

    • More noexcept here and there

    • Tiny attempts to improve the build times and produced binary size here and there, but it unfortunately shouldn't make any noticeable difference

    Source code(tar.gz)
    Source code(zip)
  • 1.1.0(Feb 18, 2018)

    This release doesn't bring many new things into cpp-sort, but has a few worthwhile bug & consistency fixes. I got a new job, hence the release name, and wanted to push everything that was ready because I might not be as active on the project for some time.

    There were a few global efforts to reduce unneeded template instantiations, reduce the produced binary size and improve compile times a bit, but these changes are anecdotal at best, and probably don't make a noticeable difference.

    New features

    • New measure of presortedness: probe::mono, after the equivalent Mono described in Sort Race by Zhang, Meng and Liang

    Bug fixes

    • Fix compiler error in hybrid_adapter when too many sorters of the same category are passed
    • Make sure all adapted sorters can also be converted to function pointers
    • Fix probe::runs: it only took increasing sequences into account and didn't behave properly with non-increasing ones (where several elements in an increasing sequence compare equivalent)
    • Properly perfect-forward iterable parameters in hybrid_adapter
    • Actually provide container_aware_adapter when including <cpp-sort/adapters.h>
    • Apply utility::as_function to the comparison and projection functions passed to self_sort_adapter, fixing a few errors when it is used with pointers to class members

    Tiny improvements

    • Don't copy instances of locale in case_insensitive_less
    • Actually create a minimal number of poplars in poplar_sorter, even in corner cases
    • Tiny optimization in indirect_adapter
    • Don't wrap adapters in sorter_facade when they don't need to, slightly reducing the template "stack traces" when there are errors
    • Small changes here and there to reduce the binary size a bit


    • Set up code coverage via (#120)
    • Globally document exception guarantees for the library (#105)
    • Enable ccache for clang++ with the Linux CI
    • Simpler and more consistent .travis.yml where possible
    Source code(tar.gz)
    Source code(zip)
  • 1.0.0(Jan 20, 2018)

    This release is merely a point in time where the project starts being versioned. A changelog would be meaningless since there is nothing to compare it against.

    Source code(tar.gz)
    Source code(zip)
I like stuff. Maybe even you.
Sorting algorithms & Big O

[![Contributors][contributors-shield]][contributors-url] [![Forks][forks-shield]][forks-url] [![Stargazers][stars-shield]][stars-url] Sorting algorith

Joseph Mahiuha 1 Nov 7, 2021
Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays.

Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.

Lakshan Sandanayaka 4 Jan 2, 2023
C++17 (-O2) template for competitive programming algorithms, which contains numerous math algorithms.

cpplibForCP C++17 (-O2) template for competitive programming algorithms, which contains numerous math algorithms. Aims: build a stable, fast, easy-to-

null 33 Nov 25, 2022
A library of common data structures and algorithms written in C.

C Algorithms The C programming language includes a very limited standard library in comparison to other modern programming languages. This is a coll

Simon Howard 2.9k Jan 9, 2023
Collection of various algorithms in mathematics, machine learning, computer science, physics, etc implemented in C for educational purposes.

The Algorithms - C # {#mainpage} Overview The repository is a collection of open-source implementation of a variety of algorithms implemented in C and

The Algorithms 15.3k Jan 5, 2023
Algorithms & Data structures in C++.

Algorithms & Data Structures in C++ 目标 ( goal ) : 经典的算法实现 (classical algorithms implementations) 服务器端 (based on linux/gcc) 正确,易于使用和改造, 一个头文件一个算法,并附带一个

xtaci 4.7k Dec 30, 2022
Several algorithms and data structures implemented in C++ by me (credited to others where necessary).

Algorithms This repository contains my implementations of several algorithms and data structures in C++ (credited to others where necessary). It has i

Petar Veličković 589 Dec 19, 2022
C++ implementations of well-known (and some rare) algorithms, while following good software development practices

ProAlgos: C++ This project is focused on implementing algorithms and data structures in C++, while following good software engineering practices, such

ProAlgos 485 Dec 7, 2022
Collection of algorithms and data structures in C++ and Java

Collection of algorithms and data structures in C++ and Java

Andrei Navumenka 1.7k Jan 2, 2023
This repository contains path planning algorithms in C++ for a grid based search.

This repository contains path planning algorithms in C++ for a grid based search.

null 245 Dec 30, 2022
Provide building blocks (software, hardware and algorithms) for implementing SLAM using small sensors

RemoteSLAM The purpose of this repo is to provide the building blocks (software drivers, hardware and algorithms) for implementing SLAM systems using

Autonomous Drones Lab, Tel Aviv University 38 Jan 20, 2022
Fundamentals of Data structures and algorithms in c++

Data Structures & Algorithms About the repository: Contains theories and programming questions related to fundamentals of data structures and algorith

fifu 46 Dec 1, 2022
CXXGraph is a Header-Only C++ Library for Graph Representation and Algorithms

CXXGraph is a small library, header only, that manages the Graph and it's algorithms in C++. In other words a "Comprehensive C++ Graph Library".

ZigRazor 186 Dec 29, 2022
Library for building multi-level indoor routes using routing algorithms.

Library for building multi-level indoor routes using routing algorithms. You can easily construct routing graphs and find the shortest path for optimal indoor navigation.

Navigine 5 Nov 21, 2022
Header-only C++ library for robotics, control, and path planning algorithms.

Header-only C++ library for robotics, control, and path planning algorithms.

null 360 Dec 13, 2022
c++ library including few algorithms and datastructures

c++ library including few algorithms and datastructures

null 2 Dec 25, 2021
This library contains a set of algorithms for working with the routing graph.

Library for building multi-level indoor routes using routing algorithms. You can easily construct routing graphs and find the shortest path for optimal indoor navigation.

Navigine 5 Nov 21, 2022
IntX is a C++11 port of IntX arbitrary precision Integer library with speed, about O(N * log N) multiplication/division algorithms implementation.

IntX IntX is a C++11 port of IntX arbitrary precision Integer library with speed, about O(N * log N) multiplication/division algorithms implementation

Telepati 8 Dec 22, 2022
All basic algorithms for solving problems of CP

All basic algorithms for solving problems of CP

Islam Assanov 1 Nov 14, 2021