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

Answer

Keep the first-element/last-element pivot as the default in TheAlgorithms quicksort implementations and keep median-of-three, randomized pivot and introsort as separate named variants. A separate optimized variant directory preserves educational clarity while offering production-grade alternatives. Evaluation without a standardized benchmark can be done with minimal, language-agnostic checks for recursion depth and worst-case behavior on sorted input.

Confirmed facts

First-element pivot quicksort is O(n²) on already sorted or reverse-sorted input and uses recursion depth O(n) in that case. Median-of-three pivot selection reduces the likelihood of worst-case partitions on sorted data. TheAlgorithms contribution guidelines emphasize idiomatic, textbook-style code and no automated benchmark suite is currently in place. Language-specific overheads such as Python list slicing versus Rust slice references affect observed runtime independently of pivot choice.

Likely explanation

First-element pivot is closer to standard textbook pseudocode, e.g., CLRS, making the core partitioning logic easier for beginners to map. Median-of-three adds extra comparisons and index handling that increases implementation complexity and can distract from the fundamental partition step. A separate variant directory lets learners first see the naive algorithm and then compare it to industry techniques without changing the primary teaching example.

Steps for this case

• Maintain naive first-element pivot as default with README note documenting the O(n²) worst case on sorted input.
• Add an optimized variants directory with median-of-three and randomized pivot implementations, each with a brief note on trade-offs.
• Add a minimal diagnostic test per language: sort a pre-sorted array of ~10,000 elements and report recursion depth and elapsed time. A stack overflow or extreme slowdown demonstrates the worst case without full profiling.
• Compare line count and readability of naive vs median-of-three to ensure the teaching example remains accessible.

Assumption: primary goal is education, not a competitive library. If the repository goal shifts to production utility, median-of-three or introsort would be justified as default.