Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Quicksort killer comparator #178

Open
Morwenn opened this issue Dec 5, 2020 · 0 comments
Open

Quicksort killer comparator #178

Morwenn opened this issue Dec 5, 2020 · 0 comments
Labels

Comments

@Morwenn
Copy link
Owner

Morwenn commented Dec 5, 2020

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant