This implementation of QuickXSort was created to check in practice the results presented by this article.
- This algorithm uses around 20% less comparisons than std::sort,
- It requires o(n) space (recursion calls),
- Average case is O(nlogn).
- Not stable, (impossible to implement with this method)
- Worst case is O(n^2),
- Requires high number of swaps.
In theory, this should be faster than std::sort when comparison operations are expensive and swaps are cheap.
To compile use make with g++ supporting -std=c++17 To sort objects with this method simply call:
quick_merge_sort(Iterator begin, Iterator end, Comparison comp);Default comparison is specifed as std::less