Is qsort linear when sorting only two values?
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).