**This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.**

### Abstract

We give a formal proof of the well-known results about the
number of comparisons performed by two variants of QuickSort: first,
the expected number of comparisons of randomised QuickSort
(i. e. QuickSort with random pivot choice) is
*2 (n+1) H _{n} -
4 n*, which is asymptotically equivalent to

*2 n ln n*; second, the number of comparisons performed by the classic non-randomised QuickSort has the same distribution in the average case as the randomised one.