In insertion sort, we divide the sequence in two parts. One contains a sorted sequence and other contains unsorted sequence. Initially the sorted section contains only the first element and unsorted section contains all other elements.
Now, in each iteration, we place each element of the unsorted part into the sorted part by comparing one element of unsorted part with every element of sorted part and placing it at its correct position in the sorted section. This process is continued until the size of sorted section becomes equal to the size of original sequence.
Here is the visualisation of insertion sort:
Implementation of insertion sort is as follows:
Time Complexity : O( n2 )
So that’s it for this article we will be coming up with our next article on further topics very soon till then keep learning, keep coding, keep reading and keep improving !!
Happy Coding 😊
By Programmers Army