A Killer Adversary for Quicksort by M. D. McIlroy presents a method to construct quicksort-adverse data on the fly, which the goal to make most quicksort implementations go quadratic or force introsorts to fallback to their underlying O(n log n) algorithm.
Considering that one of the main of cpp-sort is to provide tools to test and compare sorting algorithms, it makes sense for the library to provide such a feature. The paper provides the code for a qsort-compatible comparison function, which we can surely reuse to make a predicate suitable for our library. There will surely be some subtle things to consider such as whether the predicate is totally in line with the library's generally guarantees and the fact that it will surely be a mutable comparison function, but I don't believe those to be obstacles to its adoption.
A Killer Adversary for Quicksort by M. D. McIlroy presents a method to construct quicksort-adverse data on the fly, which the goal to make most quicksort implementations go quadratic or force introsorts to fallback to their underlying O(n log n) algorithm.
Considering that one of the main of cpp-sort is to provide tools to test and compare sorting algorithms, it makes sense for the library to provide such a feature. The paper provides the code for a
qsort-compatible comparison function, which we can surely reuse to make a predicate suitable for our library. There will surely be some subtle things to consider such as whether the predicate is totally in line with the library's generally guarantees and the fact that it will surely be a mutable comparison function, but I don't believe those to be obstacles to its adoption.