Analysis quickselect: Median of Medians with duplicates
A common refinement to quicksort could also be used with quickselect to deal with duplicates. Instead of partitioning into two buckets, do so into three. This new partition is called the &quot;fat partition&quot;. It holds items that are equal to the current pivot. When there are no duplicates, this adds 2% overhead to the sort, according to the following paper.
See https://cs.fit.edu/~pkc/classes/writing/papers/bentley93engineering.pdf
The paper discusses several memory layouts for partition, like whether to put the fat partition in the middle or the end of the invariant array or even split it and put part at the head and part at the tail, all to reduce the number of memory swaps.
The paper quantifies the huge benefits for some extreme edge cases, like when the data is a random set of ones and zeroes. In that case, their algorithm went from being four times slower than a benchmark Unix qsort to being twice as fast, an 8x speedup by the addition of a fat partition.