Skip to main content

Insertion Sort

Learn Insertion Sort (Sorting, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Insertion Sort - O(n²) Worst, O(n) Best Builds the sorted portion one element at a time, like sorting playing cards in your hand: take the next element and shift it backward past everything bigger, until it lands in its correct spot. Stable - equal elements never jump past each other, since shifting stops at the first element that's NOT bigger. Adaptive - O(n) on an already-sorted (or nearly-sorted) array, since the inner shift loop barely runs. In-place - O(1) extra space.

More lessons in Sorting