quality:correction
Using a binary search tree

The following binary search tree (BST) corresponds to each execution of quicksort: the initial pivot is the root node; the pivot of the left half is the root of the left subtree, the pivot of the right half is the root of the right subtree, and so on. The number of comparisons of the execution of quicksort equals the number of comparisons during the construction of the BST by a sequence of insertions. So, the average number of comparisons for randomized quicksort equals the average cost of constructing a BST when the values inserted (x 1, x 2, …, x n) {\displaystyle (x_{1},x_{2},\ldots,x_{n})} form a random permutation.

Consider a BST created by insertion of a sequence (x 1, x 2, …, x n) {\displaystyle (x_{1},x_{2},\ldots,x_{n})} of values forming a random permutation. Let C denote the cost of creation of the BST. We have C = ∑ i ∑ j < i c i, j {\displaystyle C=\sum _{i}\sum _{j<i}c_{i,j}}, where c i, j {\displaystyle c_{i,j}} is a binary random variable expressing whether during the insertion of x i {\displaystyle x_{i}} there was a comparison to x j {\displaystyle x_{j}}.

By linearity of expectation, the expected value E {\displaystyle \operatorname {E} } of C is E = ∑ i ∑ j < i Pr (c i, j) {\displaystyle \operatorname {E} =\sum _{i}\sum _{j<i}\Pr(c_{i,j})}.

Fix i and j < i. The values x 1, x 2, …, x j {\displaystyle {x_{1},x_{2},\ldots,x_{j}}}, once sorted, define j +1 intervals. The core structural observation is that x i {\displaystyle x_{i}} is compared to x j {\displaystyle x_{j}} in the algorithm if and only if x i {\displaystyle x_{i}} falls inside one of the two intervals adjacent to x j {\displaystyle x_{j}}.

Observe that since (x 1, x 2, …, x n) {\displaystyle (x_{1},x_{2},\ldots,x_{n})} is a random permutation, (x 1, x 2, …, x j, x i) {\displaystyle (x_{1},x_{2},\ldots,x_{j},x_{i})} is also a random permutation, so the probability that x i {\displaystyle x_{i}} is adjacent to x j {\displaystyle x_{j}} is exactly 2 j + 1 {\displaystyle {\frac {2}{j+1}}}.

We end with a short calculation: