Insertion sort

Insertion sort is simple to implement and a stable sorting algorithm. During the process of sorting, it creates a sorted subsequence. From the unsorted subpart of the sequence, it takes one value at a time in each pass and inserts it in the sorted part of the sequence, maintaining the order in the sorted subsequence. When the last element is inserted in the sorted subsequence, we get the final sorted sequence. Hence, for a sequence of N elements, it takes N-1 passes. Remember that it does not swap values like the bubble and selection sort algorithms, but it inserts values one by one in a sorted subsequence.

We can better understand the insertion sort mechanism with the following pass-by-pass diagram:

We have a sequence of integers with elements, [12, 10, 16, 11, 9, 7]. In the first pass, it starts with 10. The already sorted subsequence has one element, 12. Element 10 is inserted in front of 12. Now we have two elements, 10 and 12, in the sorted subsequence.

We can visualize...