Insertion Sort Definition

 

A simple sorting technique that scans the sorted list, starting at the beginning, for the correct insertion point for each of the items from the unsorted list.

Similar to the way people manually sort items, an insertion sort is not efficient for large lists, but is relatively fast for adding a small number of new items periodically

 

Insertion sorting algorithm is similar to bubble sort. But insertion sort is more efficient than bubble sort because in insertion sort the elements comparisons are less as compare to bubble sort.

 

Every iteration of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain.

 

The choice of which element to remove from the input is arbitrary, and can be made using almost any choice algorithm.

 

Example :

 

 

Initially , if we take only the first element, then it can be taken as sorted , 4 in this example.

In the next iteration , take the second element and place it in order in ther sorted portion, Similarly continue till all elements are sorted.

 

 

Next... .