Insertion Sort Average II

• In general: k comparisons are required to move the key over k-1 positions.

• Exception: Both first and second positions require i-1 comparisons.

1

2

3

...

i

i-1

i-2

i-1

i-1

i-2

3

2

1

Position

...

...

Comparisons necessary to place key in this position.

Previous slide

Next slide

Back to first slide

View graphic version