Insertion sort
A simple sorting algorithm building sorted array incrementally by inserting unsorted elements. Insertion sort is O(n²) but efficient on small or partially sorted arrays. Stable sort maintaining equal element order.
Formula
Best case: O(n); Worst case: O(n²)
Real World
When Spotify adds a newly released song into an already-sorted playlist of tracks ordered by release date, insertion sort efficiently slots it into the correct position in near-linear time.
Exam Focus
Highlight that insertion sort is adaptive — state O(n) on nearly sorted data and explain why with minimal shifts.
How well did you know this?