Insertion Sort
Explore how insertion sort works by inserting elements into a sorted section one at a time. Learn about its adaptive behavior, time and space complexity, and see a JavaScript implementation. This lesson helps you grasp when and why to use insertion sort, especially for small or nearly sorted data.
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 shift right.
Algorithm
Read the algorithm carefully, and note how the inner loop moves backward through the sorted portion to make room for the key element.
Start from the second element of the list (index 1), treating the first element as already sorted.
For each ...