Insertion Sort

Insertion Sort is a simple sorting technique widely used in many situations. In this sorting algorithm we start by picking the second element as key, compare it with the first element and put it in the right position. After that, the 3rd element is selected as key and compared with the elements from 1st to 2nd position and placed in the correct position. We repeat the same till the last element. In this process we have a total of n-1 passes starting from the 2nd element to the last element. This technique is similar to how we sort playing cards in our hand. Watch the video below to understand how Insertion Sort works.



Code for Insertion Sort in Python:


Output:

Unsorted List: [16, 9, 12, 37, 5, 68, 3]
Sorted List: [3, 5, 9, 12, 16, 37, 68]