Let C be a variable denoting the number of comparisons this algorithm makes, and suppose the resulting sorted array is \ell_{1} \leq \ell_{2} \leq \cdots \leq \ell_{n}. Furthermore, let A_{i j} denote the event that this algorithm at some point compares \ell_{i} and \ell_{j}. Prove that
\mathbf{E}[C]=\sum_{1 \leq i<j \leq n} \operatorname{Pr}\left[A_{i j}\right]