Sorts from all around the web

[Morwenn]

cpp-sort already uses sorting algorithms from all around the web (pdqsort, spreadsort, timsort, etc...); adding more of them in the long run can't be that harmful. Smart people created many interesting sorting algorithms and it would be a waste not to try them all. Here is a list of interesting projects that we could use to complete the library:

• [x] BonzaiThePenguin's WikiSort, a block sort implementation.
• [x] Mrrl's GrailSort (unbuffered variant or SqrtSort variant).
• [ ] flat_stable_sort from Boost.Sort.
• [x] spinsort from Boost.Sort.
• [ ] Other algorithms from Boost.Sort: parallel_stable_sort, sample_sort, etc.
• [x] Ahmet Akkök's Exact-Sort.
• [x] Keith Schwarz's smoothsort implementation.
• [ ] khegeman's floki, which implements an aligned-accessed sort.
• [ ] Maybe parts of rantala's string-sorting library, even though the algorithms are only supposed to work with unsigned char strings.
• [ ] JuSch92's implementation of a ping-pong patience sort.
• [ ] The sequential version of SaschaWitt's IPS⁴o (in-place parallel superscalar sample sort).
• [ ] ips2ra.
• [ ] weissan's QuickXsort.
• [x] Malte Skarupke's ska_sort.
• [ ] A heapsort derived from Malte Skarupke's d-ary heap implementation
• [ ] The new version of ska_sort, by the same author.
• [x] Adrian Wielgosik's C++ implementation of a drop-merge sort. Its inv-adapting property is really interesting.
• [ ] Check what lessons can be taken from tvanslyke's optimized timsort implementation.
• [ ] Daniel J. Bernstein's djbsort (see issue #132).

There are probably even more interesting sorting algorithms around. However, adapting them is often not trivial. For example SqrtSort uses 3-way comparisons and C-isms all over the place, Exact-Sort mixes IO operations with the sorting logic, some of the algorithms simply don't have an implementation in C++... Adapting these algorithms implies that we have to adapt them to use an iterator interface, to add support for arbitrary comparison functions (or even projections) and to make them work with move-only types when possible. The sort::parallel library will probably be an interesting way to test the integration of parallel sorting algorithms in cpp-sort; floki would be a way to integrate SIMD algorithms in the library.

Reminder: ask the authors for the license when needed.

[Morwenn]

Pull request #29 adds Keith Schwartz's implementation of Dijkstra's smoothsort to the library, slightly enhanced to support projection parameters and 64-bit architectures.

[Morwenn]

Pull request #33 adds BonzaiThePenguin's WikiSort to the library, which is an implementation of Pok-Son Kim and Arne Kutzner's block sort algorithm. The implementation has been enhanced to support projection parameters.

Pull request #37 actually turns the resulting block_sorter into a buffered sorter. It makes it possible to choose how the buffer is allocated and therefore to reproduce what the different complie-time switches of the original code did, but without using the preprocessor, without altering the algorithm, and with a more extensive design.

[Morwenn]

Pull request #34 adds Ahmet Akkök's Exact-Sort to the library, enhanced to actually perform a minimal number of move operations and to support user-provided comparison and projection functions.

In the end, Exact-Sort seemed to be but an optimization over cycle sort. Commit 06ce9b54386f7aa2c3f6c69820e46aacee01547c kills exact_sorter and replaces it with a different sorting algorithm named mountain sort. It is implemented as a sorter adapter.

Commit 3aff41a2db91711ddba2bc5e65806aa33dac7265 changes the name mountain_adapter to indirect_adapter which should be clearer to most. I also realized that there is an equivalent algorithm in sort::parallel. It seems that it also performs a minimal number of move operations.

[Morwenn]

Pull request #41 adds Mrrl's GrailSort to the library as a buffered sorter (making it easy to also have SqrtSort when needed), which is an implementation of a stable sorting algorithm described by B-C. Huang and M. A. Langston. The implementation has been ported to C++ and enhanced to work with random-access iterators and to support comparison and projection parameters.

[Morwenn]

Pull request #95 adds Malte Skarupke's ska_sort to the library as a type-specific sorter, adding support for proxy iterators, a bit of standard compliance regarding reinterpretation of a floating point number into an integer, and a few compile-time checks to make sure that the sorter will only accept the types it is able to handle, causing a substitution failure otherwise.

[Morwenn]

Pull request #98 adds Adrian Wielgosik's C++ implementation of a drop-merge sort to the library, improving it with the following features:

• Support for non-default-constructible types
• Support for proxy iterators
• Support for projections
• Support for bidirectional iterators

The implementation was later simplified a bit, and a bug due to a self-move with non-trivially copyable types was fixed.

[Morwenn]

cpp-sort 1.6.0 adds Francisco José Tapia's spinsort from Boost.Sort to the library, improving it with the usual things (projections, proxy iterators, etc.).

It's worth noting that I got rid of a bunch of calls to check whether a collection is sorted or reverse-sorted that didn't seem worth keeping: I don't want to pay two O(n) operation to handle two very specific cases that are already fast enough without dedicated checks anyway.