Pattern-defeating quicksort

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

  1. . . "Pattern-defeating Quicksort". Arxiv:2106.05123 [cs]. http://arxiv.org/abs/2106.05123.

Comments


← Back to Notes