algorithm

Insertion Sort is one of sorting algorithms. Sometime called by simple insertion sort. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort, but it has various advantages:

• Simple to implement
• Efficient on (quite) small data sets
• Efficient on data sets which are already substantially sorted: it runs in O(n + d) time, where d is the number of inversions
• More efficient in practice than most other simple O(n²) algorithms such as selection sort or bubble sort: the average time is n²/4 and it is linear in the best case
• Stable (does not change the relative order of elements with equal keys)
• In-place (only requires a constant amount O(1) of extra memory space)
• It is an online algorithm, in that it can sort a list as it receives it.

  Sample code ...