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 ...)
Specialization (... is a kind of me.)
binary insertion 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.
demonstration of several sort algorithms, with particular emphasis on insertion sort; more demonstrations; a animation (Java) of insertion sort.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 12 December 2011.
HTML page formatted Mon Dec 12 10:22:39 2011.
Cite this as:
Paul E. Black, "insertion sort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 12 December 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/insertionSort.html