This is an in-place algorithm for sorting based on comparison. Here, a sub-list which is always sorted is preserved. For instance, to be sorted, the lower part of an array is retained. In this sorted sub-list, an element that is to be inserted must find its appropriate position and then it must be inserted there. Hence the word, the sort of insertion.
The array is sequentially scanned, and unsorted objects are transferred and inserted (in the same array) into the sorted sub-list. For large data sets, this algorithm is not suitable, as its average and worst-case complexity is Ο(n2), where n is the number of products.
Working
We take an unsorted array for our example.
the first two elements are compared by Insertion Sort.
Both 14 and 33 are already in ascending order, it finds. 14 is in the sorted sub-list for now.
Then Insertion Sort compares 33 with 27.
And finds that 33 is not in the correct position.
Swapping 33 for 27. It also reviews all the sub-list elements that are sorted. We can see here that only one element in the sorted sub-list is 14, and that 27 is more than 14. The sorted sub-list, therefore, remains sorted after switching
We’ve got 14 and 27 in the sorted sub-list by now. Next, you equate 33 to 10.
These values are not in a sorted order.
So we swap them.
However, swapping makes 27 and 10 unsorted.
Hence, we swap them too.
Again we find 14 and 10 in an unsorted order.
We’re exchanging them again. We have a sorted sub-list of 4 items by the end of the third iteration.
This method continues until a sorted sub-list covers all of the unsorted values. Now we can see some elements of insertion style programming.
Algorithm
Pseudocode
