Analyzing Quick-Sort

Suppose that we want to sort $x_1,x_2,\dots ,x_n$. The quick-sort algorithm is defined as follows,

1. For $n=2$, put the two values in order
2. For $n>2$, choose a random value $x_i$. Put all values smaller than $x_i$ on the left of $x_i$ and all values greater on the right of $x_i$. Run quick-sort on these two smaller subsets $[1,i-1]$ and $[i+1,n]$.

Define $X$ as the number of comparisons necessary to quick-sort $n$ distinct numbers. $E[X]$ is then a measure of the effectiveness of quick-sort.

We express $X$ as a sum of smaller random variables to make this easier. First, let’s use $[n]$ as an alias for the $n$ numbers (smallest number is $1$, second to smallest is $2$, largest is $n$). For $1\le i<j\le n$, $I(i,j)=1$ if $i$ and $j$ are directly compared. Therefore, $X=\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}I(i,j)$.

$E[X]=\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}P\{i\text{ and }j\text{ are ever compared}\}$

All values will initially be in the same bucket. $j$ and $i$ will continue to be in the same bucket until either $i$, $j$, or a number between them is chosen as a pivot. They will only be compared if one of them is chosen, otherwise they get separated forever :(

Anyways, this means $P\{i\text{ and }j\text{ are ever compared}\}=\frac{2}{j-i+1}$, so $E[X]=\sum _{i=1}^{n-1}\sum _{j=i+1}^n\frac{2}{j-i+1}$

$\sum _{j=i+1}^n\frac{2}{j-i+1}\approx {\int }_{i+1}^n\frac{2}{x-i+1}dx=[2\log (x-i+1){]}_{i+1}^n\approx 2\log (n-i+1)$

$E[X]\approx \sum _{i=1}^{n-1}2\log (n-i+1)\approx 2{\int }_1^{n-1}\log (n-x+1)dx=2{\int }_2^n\log (y)dy$
$\approx 2n\log (n)$

In big-$O$ notation, this means that quick-sort is $O(n\log n)$, as expected.