Prefer a chat interface with context about you and your work?
Quicksort Is Optimal For Many Equal Keys
I prove that the average number of comparisons for median-of-k Quicksort (with fat-pivot a.k.a. three-way partitioning) is asymptotically only a constant αk times worse than the lower bound for sorting random multisets of n elements with Ω(n∊) duplicates of each value (for any ∊ > 0). The constant is αk …