Overview
Insertion sort is a basic comparison-based sorting technique used to arrange elements (for example, numbers or strings) into a defined order. It processes the input sequentially, growing a sorted subsection at the front of the list by inserting each new element into its correct place among previously processed elements. Because of its simplicity it is often introduced early in algorithm courses and appears as a practical choice for small or nearly-sorted datasets. For general background on algorithm design and analysis see computer science resources, and for general sorting concepts see sorting fundamentals.
How insertion sort works
The algorithm maintains two parts of the array: a sorted left portion and an unsorted right portion. At each step it removes the first element of the unsorted portion (the "key") and inserts it into the proper position among the elements of the sorted portion, shifting larger elements one position to the right as needed.
- Start with the first element; it is trivially sorted.
- Take the next element as the key.
- Compare the key with elements in the sorted portion, moving from right to left.
- Shift elements greater than the key one position right to make space.
- Insert the key into its correct place and repeat until the list is sorted.
Example: given [2, 10, 4], the algorithm treats 2 as sorted, takes 10 (already in correct place), then takes 4 and shifts 10 right to insert 4 between 2 and 10. The result becomes [2, 4, 10].
Characteristics and complexity
Insertion sort is stable (it preserves the relative order of equal elements) and in-place (it requires only a small, constant amount of extra memory). Time complexity depends on the initial order of elements: best case O(n) when the input is already sorted (only one comparison per element), average and worst case O(n^2) when many elements must be shifted. Because element movement is by simple shifts rather than complex swaps, insertion sort is adaptive and performs well on nearly-sorted inputs.
Although its asymptotic cost is higher than more advanced algorithms such as quicksort or mergesort, insertion sort has low overhead for small arrays and is often faster in practice for small n or as the final phase of hybrid sorts; compare notes with other sorting methods.
History, variants and usage
Insertion sort has a long pedagogical history and forms the basis of several practical techniques. Variants include binary insertion sort, which uses binary search to locate the insertion point (reducing comparisons but not the number of element shifts), and guarded insertion that reduces boundary checks. Hybrid sorting algorithms commonly switch to insertion sort for small subarrays because it minimizes overhead and benefits from locality.
It also appears inside modern sorting implementations and libraries, and plays a role in algorithms like shell sort and adaptive routines that exploit pre-existing order. For a commonly compared algorithm, see implementations of quicksort.
When to choose insertion sort
- If the input is small or nearly sorted, insertion sort is often the fastest simple option.
- When stability and minimal extra memory are required.
- As the finishing step of hybrid sorts or when implementing simple in-place sorts for constrained environments.