A high-performance, pattern-defeating quicksort implementation designed as a drop-in replacement for C++'s std::sort.
pdqsort (pattern-defeating quicksort) is a high-performance sorting algorithm designed as a drop-in replacement for C++'s std::sort. It combines the average-case speed of quicksort with the worst-case guarantee of heapsort, while achieving linear time on inputs with specific patterns like sorted or equal elements. The algorithm improves upon introsort by detecting and breaking patterns to avoid performance degradation.
C++ developers and library authors who need a fast, deterministic sorting algorithm for performance-critical applications, such as game engines, data processing pipelines, or systems programming.
Developers choose pdqsort for its superior performance over std::sort, especially on large arrays or patterned data, its deterministic behavior, and seamless integration as a drop-in replacement without requiring extensive code changes.
Pattern-defeating quicksort.
Open-Awesome is built by the community, for the community. Submit a project, suggest an awesome list, or help improve the catalog on GitHub.
Uses median-of-3 pivot selection and insertion sort for small arrays, achieving speeds comparable to quicksort on typical data, as shown in benchmarks against std::sort.
Detects patterns like sorted or equal elements and sorts them in linear time, optimizing for common real-world inputs such as ascending or descending orders.
Switches to heapsort after detecting too many bad partitions, ensuring O(n log n) worst-case complexity and avoiding quadratic slowdowns inherent in naive quicksort.
Automatically uses branchless partitioning for arithmetic types in C++11, reducing branch mispredictions and offering significant speedups for large arrays, as detailed in the README.
Does not preserve the relative order of equal elements, which can be critical for applications relying on stable sorting, unlike std::stable_sort.
Full optimization with automatic branchless partitioning requires C++11 or higher, limiting its use in older or constrained environments without modern compiler support.
The pattern detection and heapsort fallback add layers of complexity, which might introduce subtle bugs or make performance behavior less predictable in edge cases.