A Common-Sense Guide to Data Structures and Algorithms

The Efficiency of Insertion Sort

There are four types of steps that 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 passthrough. This is because each value to the left of temp_value will always be greater than temp_value, so the passthrough will only end when the gap reaches the left end of the array.

During the first passthrough, in which temp_value is ...