Introduction to Insertion Sort

Sorting algorithm 2

Image by author

In the previous article, we looked at selection sort. Insertion sort is a simple sorting algorithm that is very similar to selection sort. Given an array of elements to be sorted, insertion sort works as follows:

• Divide the array into two subarrays: sorted and unsorted subarray (similar to that of selection sort)
• In each iteration, remove the first element from the unsorted subarray and insert it in the proper position (depending on whether to be sorted in ascending or descending order) in the sorted subarray.
• Iterate until the last element of the unsorted array is removed

Let us look at an example to clearly understand the steps. Suppose the array to be sorted is (8, 4, 6, 3, 1, 9, 5)

Image by author

Initially, the sorted subarray consists of only the first element and the unsorted subarray consists of the rest of the elements in the array as shown in the figure above. We pick the first element of the unsorted subarray, which is 4, and we have to insert it in the correct position in the sorted subarray. Since 4 < 8, we shift 8 to the right by one cell and insert 4. Now, 4 has been…