Builds a sorted prefix by inserting each new element into its correct spot.
Builds a sorted prefix by inserting each new element into its correct spot.
Time complexity: O(n²). Space complexity: O(1).
Core idea — Take each new element and slide it left into its correct spot among the already-sorted prefix.
What each pass accomplishes — After inserting the k-th element the first k+1 elements are sorted relative to each other — that sorted prefix grows by one each step (its values may still shift once later elements arrive).
Use the interactive visualizer above to run Insertion Sort on your own input and watch every comparison, swap, and operation animate step by step — pause, scrub, or replay at any speed.