Skip to main content

DSAPath7 mincore

Insertion Sort

Insertion sort builds a sorted prefix by inserting each new item into its correct position. It is quadratic in the worst case but strong on small or nearly sorted arrays.

Why This Matters

Insertion sort is the simple sort that still earns its keep. Many production sort implementations switch to insertion sort for tiny partitions because the constant factors are low.

Core Idea

Maintain a sorted prefix. Take the next item and move it left until it reaches the right position.

Worked example: sorting [4, 2, 5, 1], after reading 2 the prefix becomes [2, 4]; after 5, [2, 4, 5]; after 1, [1, 2, 4, 5].

PropertyInsertion sort
worst-case timeO(n2)O(n^2)
best-case timeO(n)O(n)
extra spaceO(1)O(1)
stableyes

Common Mistakes

  • Dismissing insertion sort because of the worst case. It can be excellent on small or nearly sorted inputs.
  • Forgetting the sorted-prefix invariant.
  • Moving items with swaps when shifting would be clearer and often cheaper.

Exercises

  • Trace insertion sort on [3, 1, 4, 2].
  • Explain why already sorted input takes linear time.
  • Compare insertion sort with bubble sort on number of swaps.

Next Topics

References

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 2.
  • Sedgewick and Wayne. Algorithms (4th ed., 2011). Ch. 2.