#### Tue Apr 20 2021

# Insertion Sort

Insertion sort is an efficient algorithm for sorting a small number of elements. Insertion sort sorts the array by shifting elements one by one. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

It is much less efficient on large lists than more advanced algorithms such as Quick Sort, Heap Sort, or merge sort. However, Insertion sort have several advantages, Like:

- It is very simple for implementation
- Efficient for small data sets
- More efficient in practice than most other simple quadratic (Worst case O(n
^{2})) algorithms such as selection sort or bubble sort - Adaptive, efficient for data sets that are already substantially sorted. The time complexity is O(n + d), where d is the number of inversions
- Stable, does not change the relative order of elements with equal keys
- In-place, only requires a constant amount O(1) of additional memory space
- Online, can sort a list as it receives it