Insertion Sort
This page gives a brief introduction to insertion sort.
Definition
Insertion sort is a simple, intuitive sorting algorithm. It splits the elements to be sorted into a "sorted" part and an "unsorted" part, and repeatedly picks one of the unsorted elements and inserts it at its correct position among the sorted ones.
Playing cards works the same way: you draw a card from the table, insert it into your hand according to its rank, and then draw the next card.
Properties
Stability
Insertion sort is a stable sorting algorithm.
Time complexity
The best-case time complexity of insertion sort is \(O(n)\), and it is very efficient when the sequence is almost sorted.
Its worst-case time complexity and average-case time complexity are both \(O(n^2)\).
Implementation
Pseudocode
1 2 3 4 5 6 7 8 9 10 11 | |
1 2 3 4 5 6 7 8 | |
1 2 3 4 5 6 7 8 9 10 11 | |
Binary insertion sort
Insertion sort can also be sped up with binary search. The gain is quite noticeable when there are many elements to sort.
Time complexity
Binary insertion sort finds each insertion position by binary search, which brings the total number of comparisons down to \(O(n\log n)\). In the worst case it still has to move \(\Theta(n^2)\) elements, though, so its worst-case time complexity is still \(\Theta(n^2)\).
Implementation
1 2 3 4 5 6 7 8 9 10 | |
This page is an unofficial English translation of the original OI Wiki page (revision b469442a), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: partychicken, 24OI-bot, ouuan, thy233, hsfzLZH1, H-J-Granger, NachtgeistW, Konano, Enter-tainer, Junyan721113, iamtwz, Xeonacid, mcendu, ksyx, Menci, AprilNEA, Great-designer, Tiphereth-A, EmptyDreams, clee01, shawlleyw, TrickEye, Molly166, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.