Insertion Sort
noun
say it: “in-SUR-shun sort” /ɪnˈsɝːʃən sɔːrt/
A simple sort that takes each item in turn and slides it left into its place among the items already sorted.
What is insertion sort?
Insertion sort sorts the way you sort a hand of cards: pick up the next card and slide it left past every bigger card into its place. It is O(n²) at worst, on a backward list, but close to O(n) on a list that's almost sorted, which is why built-in sorts use it for short stretches.
In a sentence
- “The leaderboard was almost sorted, so insertion sort only had to slide the three new scores into place.”
Level: Apprentice · More Data Structures terms at this level
Updated