Insertion sort

Insertion sort is a simple sorting algorithm that builds a sorted sequence one element at a time. It works by taking each element from the input and inserting it into its correct position among the already-sorted elements. On small arrays — typically fewer than 20 elements — insertion sort is faster than more complex algorithms like quicksort because of its low overhead and excellent cache locality.

The algorithm is stable (preserves the relative order of equal elements) and in-place (requires only O(1) additional memory). Its worst-case and average-case time complexity is O(n²), making it unsuitable for large datasets. However, it is often used as the base case in hybrid sorting algorithms like introsort and Timsort, where recursive algorithms switch to insertion sort for small subarrays.