# 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?

• First of all, "QuickSort" isn't actually an algorithm, it's a family of algorithms depending upon how you pick the pivot, and how you divide equal elements. The answer here will strongly depend upon those choices. It's not too hard to see that choosing poorly will still result in $O(n^2)$ worst-case behavior. Whether you can do better isn't as clear. – Mark Reitblatt Feb 4 '11 at 21:34
• The standard implementation of quicksort should never be linear ... the best possible running time would be $n \log_2 n$. – Peter Shor Feb 4 '11 at 21:46
• I think the answer is something like is. All elements are either 1 or 2. Pick your pivot arbitrarily. After the scanning phase, you're automatically sorted. – Suresh Venkat Feb 4 '11 at 22:03
• If you exclude elements equal to the pivot from the recursion, you end at depth 2. But I don't think that's the standard version. – Marcus Ritt Feb 4 '11 at 22:56
• @Suresh: yes, but the usual algorithm doesn't detect this. – Marcus Ritt Feb 4 '11 at 23:25

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).