Insertion Sort: Analysis

• Worst Case: Keys are in reverse order

• Do i-1 comparisons for each new key, where i runs from 2 to n.

• Total Comparisons: 1+2+3+ … + n-1

Previous slide

Next slide

Back to first slide

View graphic version