Help us to keep this website almost Ad Free! It takes only 10 seconds of your time:

When we analyze the performance of the sorting algorithm, we interest primarily on the number of comparison and exchange.

Let E_{n} be the total average number of exchange to sort array of N element. E_{1} = 0 (we do not need any exchange for array with one element). The average number of exchange to sort N element array is the sum of average number of number of exchange to sort N-1 element array with the average exchange to insert the last element into N-1 element array.

Simplify the summation (arithmetic series)

Expands the term

Simplify the summation again (arithmetic series)

Let C_{n} be the total average number of comparison to sort array of N element. C_{1} = 0 (we do not need any comparison on one element array). The average number of comparison to sort N element array is the sum of average number of number of comparison to sort N-1 element array with the average comparison to insert the last element into N-1 element array. If last element is largest element, we need only one comparison, if the last element is the second smallest element, we need N-1 comparison. However, if last element is the smallest element, we do not need N comparison. We still only need N-1 comparison. That is why we remove 1/N in below equation.

Simplify the summation (arithmetic series)

Expand the term

Simplify the summation again (arithmetic series and harmonic number)