Is qsort linear when sorting only two values? This CodeGolf answer suggests that quick sorting an array whose elements can take only two values is linear. Can this assumption be proved?
There is a large body of research on Quicksort for sorting multisets.
The talk Quicksort is optimal by Sedgewick gives a nice overview of this.
Basically with 3-way partitioning you get within a constant of the information theoretic minimum. The information theoretic minimum is: Suppose we are to sort $n$ keys, where there is only $m$ distinct keys, and the $i$th key occurs $n_i$ times. Then we need 
$n \lg(n) - \sum_{i=1}^m n_i\lg n_i -n \lg e +O(\lg n)$ three way comparisons on the average. (See "Sorting multisets and vectors in-place", by Munro and Raman).