Learning Functional Data Structures and Algorithms

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 ...