A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

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 tempValue. In a worst-case scenario, where the array is sorted in reverse order, we have to compare every number to the left of tempValue with tempValue in each pass-through. This is because each value to the left of tempValue will always be greater than tempValue, so the pass-through will only end when the gap reaches the left end of the array.

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