First-Element Pivot vs. Median-of-Three: Default Quicksort Strategy for Sorted Input Resilience

TheAlgorithms repository provides quicksort implementations across 30+ languages with a stated goal of educational clarity. Current default implementations in many languages select the first or last element as pivot, causing O(n²) degradation on already-sorted or reverse-sorted input. Contribution guidelines emphasize idiomatic, textbook-style code but do not specify performance requirements, and no automated benchmark suite exists to detect regressions when algorithms are refactored.

A 2023 proposal to introduce a "performance" tag or separate optimized variants (such as introsort or median-of-three pivot selection) was closed without consensus. Maintainers prefer keeping implementations close to pseudocode, while some contributors argue that quadratic worst-case behavior misleads learners about practical algorithm performance. Language-specific factors—such as Python list slicing overhead versus Rust slice references—further complicate a uniform policy.

Should the default quicksort implementation adopt median-of-three pivot selection across languages to avoid quadratic behavior on sorted input? Would adding a separate "optimized" variant directory preserve educational clarity while offering production-grade alternatives? How can maintainers evaluate this trade-off without a standardized benchmark suite?