Insertion Sort
Explore how insertion sort works by inserting one element at a time into the correct position in a sorted list. Learn its step-by-step algorithm, Python implementation, and how its performance varies with input order. Understand its time and space complexity, advantages for small or nearly sorted datasets, and when to apply this efficient sorting method.
Imagine you are holding a hand of playing cards. You do not sort all the cards at once. Instead, you take one card at a time and insert it into the correct position among the cards already arranged in your hand.
That is exactly what Insertion Sort does. It treats the left side of the list as already sorted, picks the next element, and inserts it into the correct position within that sorted portion.
Insertion sort is a sorting algorithm that builds a sorted section from left to right by taking one element at a time and inserting it into its correct position among the previously sorted elements.
Why this intuition matters: Unlike selection sort, which searches for a minimum and swaps it, insertion sort focuses on placing the current element exactly where it belongs. This makes its behavior more natural on nearly sorted input.
How insertion sort works
Insertion sort starts at index 1 because a single element at index 0 is already sorted on its own. From there, each pass inserts one new element into the correct position within the sorted left portion.
Take the current element as the key.
Compare it with the elements to its left.
Shift every larger element one position to the right.
Insert the key into the gap that remains.
Key insight: Insertion sort shifts elements instead of swapping them. This is one reason it stays stable. In the standard implementation, equal elements do not jump past one another.
Interactive animation
The visualizer below shows how the key moves left while larger elements ...