Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
| Name | Best | Average | Worst | Memory | Stable |
|---|---|---|---|---|---|
| Insertion sort | n | n2 | n2 | 1 | Yes |