Sort an array in increasing order. Insertion sort works like sorting playing cards in your hand.
DSA Animator › DSA Revision › Sorting Algorithms › Insertion Sort
Remember: shift bigger values right, then drop the key into the gap. Insertion sort shines on small or nearly sorted inputs. The video solves Insertion Sort (LeetCode 912, Easy) with the Insert into Sorted Prefix pattern from the Sorting Algorithms topic, and you can replay every step in the interactive Insertion Sort animation.
Sort an array in increasing order. Insertion sort works like sorting playing cards in your hand.
For 5, 2, 8, 1, 9, 3, the result is 1, 2, 3, 5, 8, 9.
It is O of n squared in the worst case. But on nearly sorted data it is very fast, which is why libraries use it for small parts.
Keep the left part of the array sorted. Take the next value as the key. Shift every bigger value in the sorted part one step to the right. Drop the key into the gap that opens up. Repeat until the whole array is the sorted part.
The key 2 is smaller than 5, so 5 shifts right, and 2 goes first. The key 8 is bigger than 5, so it stays where it is. The key 1 shifts 8, 5 and 2 to the right, and goes to the front. 9 stays where it is. The key 3 shifts 9, 8 and 5, and lands after 2. The array is 1, 2, 3, 5, 8, 9.
In code, loop i from 1 to the end, and store a of i as key. Set j to i minus 1, and while j is valid and a of j is bigger than key, copy a of j to the right and decrease j. Place the key at j plus 1. It's O of n squared in the worst case, O of n on sorted input, and O of 1 space.
Remember: shift bigger values right, then drop the key into the gap. Insertion sort shines on small or nearly sorted inputs.