NIST

insertion sort

(algorithm)

Definition: Sort by repeatedly taking the next item and inserting it into the final data structure in its proper order with respect to items already inserted. Run time is O(n2) because of moves.

Also known as linear insertion sort.

Generalization (I am a kind of ...)
sort.

Specialization (... is a kind of me.)
binary insertion sort.

Aggregate parent (I am a part of or used in ...)
q sort.

See also gnome sort.

Note: Sorting can be done in place by moving the next item into place by repeatedly swapping it with the preceding item until it is in place - a linear search and move combined. This implementation is given in C. J. Shaw and T. N. Trimble, Algorithm 175 Shuttle Sort, CACM, 6(6):312-313, June 1963.

If comparing items is very expensive, use binary search to reduce the number of comparisons needed to find where the item should be inserted, then open a space by moving all later items down one. However a binary search is likely to make this not a stable sort.

Author: PEB

Implementation

An implementation (Java) due to Sedgewick and Wayne (search for Insertion sort). Algorithms and Data Structures' explanation and code (Java and C++). Other implementations may be available through the Stony Brook Algorithm Repository, Sorting. (Fortran). Flower Brackets using scanners, objects, and recursion (Java). (Python). use binary search to find where to insert (Python).

More information

Insertion sort illustrated followed by a race between insertion sort and bubble sort and then analysis of bubble sort, insertion sort, and quick sort.

A race between Shell sort and insertion sort followed by a race between them where Shell sort has a gap sequence optimized for 10 items.

Insertion sort illustrated through a Romanian folk dance. Created at Sapientia University.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 6 April 2023.
HTML page formatted Thu Apr 6 14:40:22 2023.

Cite this as:
Paul E. Black, "insertion sort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 6 April 2023. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/insertionSort.html