Insertion sort algorithm sorts a list of values by repeatedly inserting a new element into a sorted sublist until the whole list is sorted. Starting out, the sorted sublist is the list of size 1 which is the first element in the list. It then inserts the second element to the list by comparing with the element in the list and so on. For the thirde element, it compares the element with the sorted sub-list of size 2. It will move the larger elements to the right and insert the element in the appropriate position in the sub list.
With each element being processed, the sublist size increments by one until all the elements are processed.
Exercise: Write an implementation for Insertion Sort.
Before sort:
List is : [69, 4, 2, 10, 60, 50, 59, 11, 7, 70, 66, 79, 45 ]
After sort:
List is : [2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79 ]
Download Code: Insertion Sort