A Common-Sense Guide to Data Structures and Algorithms

Insertion Sort

We’ve previously encountered two different sorting algorithms: Bubble Sort and Selection Sort. Both have efficiencies of O(N²), but Selection Sort is actually twice as fast. Now we’ll learn about a third sorting algorithm called Insertion Sort that will reveal the power of analyzing scenarios beyond the worst case.

Insertion Sort consists of the following steps:

1. In the first passthrough, we temporarily remove the value at index 1 (the second cell) and store it in a temporary variable. This will leave a gap at that index, since it contains no value:

   

   In subsequent passthroughs, we remove the values at the subsequent indexes.

2. We then ...