We’ve previously encountered two different sorting algorithms: Bubble Sort and Selection Sort. Both have efficiencies of O(N2), 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:
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.
We then ...