The insertion sort is a simple sorting algorithm. It iteratively builds the sorted output one element at a time.
While insertion sort's worst-case and average complexities are both O(n2), it is one of the fastest algorithms for sorting very small arrays, and as such is often used to complement other algorithms such as quicksort below a certain number of elements.
Insertion sort is useful for nearly-sorted arrays, as complexity is O(nk) when each element is no more than k places away from its sorted position.
It is a stable in-place sort, requiring a constant amount of memory. Any items with identical keys in the input will remain in the same order when output.
