Question

How many comparisons does the insertion sort use to sort the list 1,2,3,…,n?

Short answer

The number of comparisons to sort 1,2,..,n using insertion sort is,

$\frac{n(n-1)}{2}$.

Step-by-step solution

Step 1

In first step, we will consider 1^st pass.

We will compare only two elements.

So we need only one comparison.

Step 2

In second step, we will consider 2^nd pass.

We will compare third element with the 1^st and 2^ndelements.

So we need two comparisons.

Step 3

Likewise we consider up to (n-1)^th pass.

At that pass we compare n elements with the previous (n-1) elements..

Therefore we need n-1 comparisons.

Step 4

We have n elements in our list.

The number of comparison needed is

1+2+3+…+(n-1).

We see that this is the sum of n positive number ,

Total number of comparison is$\frac{n(n-1)}{2}$ .

Final answer                                                                                                                        

The number of comparisons to sort 1,2,..,n using insertion sort is,

$\frac{n(n-1)}{2}$.