View source for 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.

[[Category:Computer Science]] [[Category:Algorithms]]