- tags
- Algorithm
- resources
- Youtube, (Peters 2021)
This is a sorting algorithm based on the well known quicksort algorithm. It uses an number of optimizations on top of the base algorithm:
- Pivot selection
- Branchless partitioning
- Insertion sort base case
- Bounds check elimination
- Optimistic pre-sortedness
- Many equal values
- Breaking self-similarity
- \(O(n^2)\) worst-case prevention
Bibliography
- Orson R. L. Peters. . "Pattern-defeating Quicksort". Arxiv:2106.05123 [cs]. http://arxiv.org/abs/2106.05123.