A randomized algorithm for sorting. pick a pivot partition the array into bigger and less than the pivot (see k-select) recurse on L, R return concatenated L, pivot, R additional information stability quicksort is not stable (it doesn’t preserve equal elements’ order). recurrence relationship \begin{equation} T\left(n\right) = T\left(|L|\right) + T\left(|R|\right) + O\left(n\right) \end{equation} recurse on left, recurse on right, the partitioning. In an idea world, suppose the array is split exactly in half, then:

which would be n \log \left(n\right) expected running time Whether or not a pair of variables is compared is a random variable. Notice that a pair of values in quicksort is either compared once (because they were a pivot-value pair) or compared never (because they are in two arms of recursive calls). Now, we can write:

where X_{a,b} \in \left\{0,1\right\} is whether or not a,b is compared. By linearity of expectation:

We have X_{a,b}=0 if any value between them (i.e. \left(a,b\right)) is chosen first as a pivot (i.e. such that a,b would then be separated into two parts). And so, P\left(X_{a,b}=1\right) is equivalently the probability of a or b being picked first out of [a,b] for pivots (i.e. instead of numbers between them as pivots). The probability of this is P\left(X_{a,b} = 1\right) = \frac{2}{b-a+1}. So, plunging this in, we will obtain:

worst-case running time The worst case running time is choosing pivots that are always the maximum or minimum pivot, which just means that we keep merging, which is O\left(n^{2}\right). doing it in place pick a pivot swap pivot with whatever the last element of the list is (i.e. such that the pivot is at the end) initialize two pointers a,b increment b; when b sees something smaller than the pivot, swap a,b pointed values, and then increment a and b Intutition: everything before a is smaller than the pivot; everything after a and before b is larger than the pivot, everything else is after b.