Insertion sort is divided into two parts:
1. Straight Insertion Sort
2. Shell Sort
Insertion sort is a simple sort algorithm, a comparison sort in which the sorted array [or list] is built one entry at a time. It is much less efficient on large lists than the more advanced Algorithms such as Quick sort, Merge sort or Heap sort.
