Quicksort compare analysis

Quicksort user $~2NlnN$ compares to sort
an array of N distinct keys on average
(one-sixth that many exchanges)

Proof

Let $C_N$ be the average number of compares need to sort N items
with distinct values.
We have $C_0=C_1=0$ for $N>1$

Express the average compare

$$C_N = N + 1 + (C_0+C_1+...+C_{N-2}+C_{N-1})/N + (C_{N-1}+C_{N-2}+...+C_0)/N$$

1. cost of partitioning
   N-1 compares two partition with flag
   1 more compare in each part breakpoint compare

1. left subarray sort

   $$(C_0+C_1+...+C_{N-2}+C_{N-1})/N$$

2. right subarray sort

   $$(C_{N-1}+C_{N-2}+...+C_1+C_0)/N$$

Rearrange terms

1. Multiplying by N

$$NC_N = N(N+1) + 2(C_0+C_1+...+C_{N-2}+C_{N-1})$$

1. Subtracting with same equation of N-1

$$NC_N - (N-1)C_{N-1} = N(N+1)-(N-1)N +$$ $$2(C_0+C_1+...+C_{N-2}+C_{N-1}) - 2(C_0+C_1+...+C_{N-2})$$ $$\Rightarrow$$ $$NC_N - (N-1)C_{N-1} = 2N + 2C_{N-1}$$

1. Each item dividing by N(N+1) leaves

$$C_N/(N+1) = C_{N-1}/N + 2/(N+1)$$

1. Add same equation from 1

$$C_N/(N+1) = C_{N-1}/N + 2/(N+1)$$ $$+$$ $$C_{N-1}/(N) = C_{N-2}/(N-1) + 2/(N)$$ $$\cdots$$ $$C_3/(4) = C_2/3 + 2/4$$ $$+$$ $$C_2/(3) = C_1/2 + 2/3$$ $$\Rightarrow$$ $$\frac{C_2}{3} + \frac{C_3}{4}+...+\frac{C_{N-1}}{N} + \frac{C_N}{N+1}=$$ $$\frac{C_1}{2} + \frac{C_2}{3}+...+\frac{C_{N-2}}{N-1} + \frac{C_{N-1}}{N} + \frac{2}{3} + \frac{3}{4}+...+\frac{2}{N} + \frac{2}{N+1}$$ $$\Rightarrow$$ $$\frac{C_N}{(N+1)} = \frac{C_1}{2}+\frac{2}{3} + \frac{3}{4}+...+\frac{2}{N+1}$$ $$\Rightarrow$$ $$C_N \sim 2(N+1)(\frac{1}{3}+\frac{1}{4}+...+\frac{1}{N+1})$$

1. Further integration

$$\frac{1}{3}+\frac{1}{4}+...+\frac{1}{N+1} \sim ln(N)$$ $$\Rightarrow$$ $$C_N \sim 2NlnN \approx 1.39lgN$$

PS.

$$1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{N}>ln(1+1)+ln(1+\frac{1}{2})+$$ $$...+ln(1+\frac{1}{N-1})+ln(1+\frac{1}{N})$$ $$\Rightarrow$$ $$1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{N} > ln[2 \times \frac{3}{2} \times \frac{4}{3} \times ...\frac{N}{N-1} \times \frac{N+1}{N}] \approx ln(N)$$