Intro to Python for Computer Science and Data Science: Learning to Program with AI, Big Data and The Cloud

11.12 Insertion Sort

Insertion sort is another simple, but inefficient, sorting algorithm. The first iteration of this algorithm takes the second element in the array and, if it’s less than the first element, swaps it with the first element. The second iteration looks at the third element and inserts it into the correct position with respect to the first two, so all three elements are in order. At the ith iteration of this algorithm, the first i elements in the original array will be sorted.

Consider as an example the following array, which is identical to the one used in the discussion of selection sort.

34 56 14 20 77 51 93 30 15 52

A program that implements the insertion sort algorithm will first look at the first two elements of the array, ...