Editing Introsort (section)

=== pdqsort ===
Pattern-defeating quicksort (pdqsort) is a variant of introsort developed by Orson Peters, incorporating the following improvements:<ref>{{cite web |last1=Peters|first1=Orson R. L. |title=orlp/pdqsort: Pattern-defeating quicksort. |url=https://github.com/orlp/pdqsort |website=GitHub |year=2021 |language=en |arxiv=2106.05123}}</ref>
* Median-of-three pivoting,
* "BlockQuicksort" partitioning technique to mitigate branch misprediction penalities,
* Linear time performance for certain input patterns ([[adaptive sort]]),
* Use element shuffling on bad cases before trying the slower heapsort.
* Improved adaptivity for low-cardinality inputs

Pdqsort is used by [[Rust (programming language)|Rust]], [[GAP (computer algebra system)|GAP]],<ref>{{cite web |title=slice.sort_unstable(&mut self) |url=https://doc.rust-lang.org/std/primitive.slice.html#method.sort_unstable |website=Rust |quote=The current algorithm is based on pattern-defeating quicksort by Orson Peters, which combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on slices with certain patterns. It uses some randomization to avoid degenerate cases, but with a fixed seed to always provide deterministic behavior.}}</ref> and the C++ library [[Boost (C++ libraries)|Boost]].<ref>{{cite conference |last1=Lammich |first1=Peter |title=Efficient Verified Implementation of Introsort and Pdqsort |doi-access=free |conference=IJCAR 2020: Automated Reasoning |date=2020 |volume=12167 |pages=307–323 |doi=10.1007/978-3-030-51054-1_18}}</ref>