This is a sorting algorithm that uses in-place comparisons. A sub-list is kept here that is always sorted. For instance, the lower part of an array is kept in order to be sorted. An element that is to be ‘inserted’ into this sorted sub-list must first identify its right spot and then be inserted there. As a result, the term “insertion sort” was coined.
Unsorted items are moved and added to the sorted sub-list as the array is scanned progressively (in the same array). Because its average and worst-case complexity are Ο(n2), where n is the number of items, this approach is not suitable for huge data sets.
Now we have a bigger picture of how this sorting technique works, so we can derive simple steps by which we can achieve insertion sort.
Step 1 − If it is the first element, it is already sorted. return 1; Step 2 − Pick next element Step 3 − Compare with all elements in the sorted sub-list Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be sorted Step 5 − Insert the value Step 6 − Repeat until list is sorted
procedure insertionSort( A : array of items ) int holePosition int valueToInsert for i = 1 to length(A) inclusive do: /* select value to be inserted */ valueToInsert = A[i] holePosition = i /*locate hole position for the element to be inserted */ while holePosition > 0 and A[holePosition-1] > valueToInsert do: A[holePosition] = A[holePosition-1] holePosition = holePosition -1 end while /* insert the number at hole position */ A[holePosition] = valueToInsert end for end procedure