Insertion sort builds a final sorted list one item at a time. It’s much less efficient on large lists than more advanced algorithms like quicksort or merge sort.

Pseudocode

• For each index in the input list:
  • Set a j variable to the current index
  • While j is greater than 0 and the element at index j-1 is greater than the element at index j:
    • Swap the elements at indices j and j-1
    • Decrement j by 1
• Return the list

It has O(n^2) in worst case scenario, O(n) in best case.

Why use insertion sort

• Simple implementation, easy to write
• Fast for very small data sets
• Faster than other simple sorting algorithms like Bubble Sort
• Adaptive: Faster for partially sorted data sets
• Stable: Does not change the relative order of elements with equal keys
• In-Place: Only requires a constant amount of memory
• Online: Can sort a list as it receives it

Some production sorting implementations use insertion sort for very small inputs under a certain threshold (very small, like 10-ish). Insertion sort is better for very small lists than some of the faster algorithms because:

• There is no recursion overhead
• Tiny memory footprint
• It’s a stable sort.

References

• boot.dev

Next -> quicksort-algorithm