A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

The Efficiency of Insertion Sort

Four types of steps occur in Insertion Sort: removals, comparisons, shifts, and insertions. To analyze the efficiency of Insertion Sort, we need to tally up each of these steps.

First, let’s dig into comparisons. A comparison takes place each time we compare a value to the left of the gap with the temp_value. In a worst-case scenario, where the array is sorted in reverse order, we have to compare every number to the left of temp_value with temp_value in each pass-through. This is because each value to the left of temp_value will always be greater than temp_value, so the pass-through will only end when the gap reaches the left end of the array.

During the first pass-through, in which temp_value is the value at ...