<p>Depends on the exact implementation.</p>

<p>If you check for already-sorted arrays, then qsort stops after the initial pass, so is O(n).</p>

<p>If, as Marcus suggested, you perform a three-way partition into x&lt;pivot, x=pivot, and x&gt;pivot and don't sort the middle partition, then the recursion stops at a depth of 2, and so is still O(n).</p>

<p>If you <em>don't</em> check for already-sorted arrays and don't exclude elements equal to the pivot from recursion, then the number of elements to sort only decreases by 1 every time, so your qsort would be O(n&sup2;).</p>

CC BY-SA 2.5
2011-02-05T06:05:57.247Z
2011-02-05T06:05:57.247Z
dan04
<p>There is a large body of research on Quicksort for sorting multisets.
The talk <a href="http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf">Quicksort is optimal</a> 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).</p>

CC BY-SA 2.5
2011-02-05T18:32:42.427Z
excellent. that's a great answer.
Suresh Venkat
CC BY-SA 2.5
2011-02-05T11:02:26.333Z
2011-02-06T13:29:33.783Z
2011-02-06T13:29:33.783Z
Kristoffer Arnsfelt Hansen
<p><a href="https://codegolf.stackexchange.com/questions/504/stable-positive-negative-separation/508#508">This</a> CodeGolf answer suggests that quick sorting an array whose elements can take only two values is linear. Can this assumption be proved?</p>

CC BY-SA 2.5
2011-02-04T21:34:29.850Z
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
CC BY-SA 2.5
2011-02-04T21:38:00.910Z
Concretely, suppose we always pick the first element as pivot, and equal elements are treated as "larger". Now, give it an already sorted list. You will perform recursive calls to depth $O(n)$ and at each call you will only decrease the size of the argument by 1.
Mark Reitblatt
CC BY-SA 2.5
2011-02-04T21:46:42.570Z
The standard implementation of quicksort should never be linear ... the best possible running time would be $n \log_2 n$.
Peter Shor 
CC BY-SA 2.5
2011-02-04T21:59:01.470Z
Isn't the question confusing asymptotic analysis with a fixed input size? On 'n' elements every decider runs in precisely worst case constant time (this constant may be large, but I could tell you it exists). It's like asking is $x^2$ for $x=n$ quadratic? The question is ill-posed or I don't get the spirit of the question.
Ross Snider
CC BY-SA 2.5
2011-02-04T22:02:08.533Z
The domain is of size 2, not the array.
Suresh Venkat
CC BY-SA 2.5
2011-02-04T22:03:30.403Z
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
CC BY-SA 2.5
2011-02-04T22:08:04.090Z
Oh, that's silly of me. I did miss the spirit of the question. *Tips hat*
Ross Snider
CC BY-SA 2.5
2011-02-04T22:56:01.643Z
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
CC BY-SA 2.5
2011-02-04T23:13:18.173Z
@Marcus, but the point is that there is no need for recursion.
Suresh Venkat
CC BY-SA 2.5
2011-02-04T23:25:16.460Z
@Suresh: yes, but the usual algorithm doesn't detect this.
Marcus Ritt
CC BY-SA 2.5
2011-02-04T23:59:09.680Z
oh I see. the algorithm doesn't know the special structure. that's what your comment refers to re: depth 2
Suresh Venkat
CC BY-SA 2.5
2011-02-05T11:09:57.200Z
@Marcus: I hope it does! Otherwise as dan04 points out in his answer you get a quadratic runtime.
Kristoffer Arnsfelt Hansen
<ds.algorithms><time-complexity><sorting>
Is qsort linear when sorting only two values?
Alexandru
# Is qsort linear when sorting only two values?

(Asked by: username_0 on 2011-02-04)

[This](https://codegolf.stackexchange.com/questions/504/stable-positive-negative-separation/508#508) CodeGolf answer suggests that quick sorting an array whose elements can take only two values is linear. Can this assumption be proved?

**Tags:** ds.algorithms, time-complexity, sorting
> **Comments:**
> **username_1**: 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.  
> **username_1**: Concretely, suppose we always pick the first element as pivot, and equal elements are treated as "larger". Now, give it an already sorted list. You will perform recursive calls to depth $O(n)$ and at each call you will only decrease the size of the argument by 1.  
> **username_2**: The standard implementation of quicksort should never be linear ... the best possible running time would be $n \log_2 n$.  
> **username_3**: Isn't the question confusing asymptotic analysis with a fixed input size? On 'n' elements every decider runs in precisely worst case constant time (this constant may be large, but I could tell you it exists). It's like asking is $x^2$ for $x=n$ quadratic? The question is ill-posed or I don't get the spirit of the question.  
> **username_4**: The domain is of size 2, not the array.  
> **username_4**: 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.  
> **username_3**: Oh, that's silly of me. I did miss the spirit of the question. *Tips hat*  
> **username_5**: 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.  
> **username_4**: @Marcus, but the point is that there is no need for recursion.  
> **username_5**: @Suresh: yes, but the usual algorithm doesn't detect this.  
> **username_4**: oh I see. the algorithm doesn't know the special structure. that's what your comment refers to re: depth 2  
> **username_6**: @Marcus: I hope it does! Otherwise as dan04 points out in his answer you get a quadratic runtime.  

---

## 2 answers

### Answer by username_6 on 2011-02-05. Score: 20 | Accepted answer

There is a large body of research on Quicksort for sorting multisets.
The talk [Quicksort is optimal](http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf) 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).

> **Comments:**
> **username_4**: excellent. that's a great answer.  

---

### Answer by username_7 on 2011-02-05. Score: 6

Depends on the exact implementation.

If you check for already-sorted arrays, then qsort stops after the initial pass, so is O(n).

If, as Marcus suggested, you perform a three-way partition into xpivot and don't sort the middle partition, then the recursion stops at a depth of 2, and so is still O(n).

If you *don't* check for already-sorted arrays and don't exclude elements equal to the pivot from recursion, then the number of elements to sort only decreases by 1 every time, so your qsort would be O(n²).


---

