Insertion Sort —
Build the sorted part one card at a time.
Insertion sort works the way most people sort a hand of playing cards: keep a sorted section at the front, and slide each new element left into its correct spot within that section. Watch each element find its place on LearnBug and see why this is fast on nearly-sorted data specifically.
What is Insertion Sort?
Treat the first element as a trivially-sorted section of size 1. For every element after it, hold it aside as the "key," then shift elements in the sorted section rightward as long as they're bigger than the key, until you find the key's correct spot — then drop it in. The sorted section grows by one element every step.
Why visualization helps
The inner while loop's shifting can look like it's doing the same thing as bubble sort's swapping, but it's meaningfully different — it's shifting elements to make room, not exchanging pairs. LearnBug shows the sorted/unsorted boundary moving and the shifting happen distinctly, so the difference from bubble sort is visible, not just described.
Shifting, not swapping
A growing sorted prefix
The array is always split into a sorted left section and an unsorted right section — the boundary moves one step right after every element is inserted.
Shift right, don't pairwise swap
Elements bigger than the key move one slot right to make room — the key isn't exchanged with each one individually, it's placed once it finds its spot.
Nearly-sorted input is nearly free
If each new element is already close to its correct spot, the inner while loop barely runs — this is where insertion sort genuinely beats other O(n²) sorts in practice.
Sorting [5, 2, 4, 6, 1, 3]
Sorted section = [5]. Key = 2. Shift 5 right, insert 2 at the front
2 < 5, so 5 shifts one spot right to make room, and 2 drops into position 0. Sorted section grows to [2, 5].
Key = 4. Shift 5 right (4 < 5), stop at 2 (4 > 2) — insert 4 between them
Only one shift needed this time — 4 only needs to move past 5, not all the way to the front. Sorted section: [2, 4, 5].
Key = 6. Already bigger than everything sorted — zero shifts, stays put
6 is compared to 5 first, and since 6 > 5, the while loop condition is immediately false — no shifting happens at all. This is the "best case" behavior showing up mid-array.
Key = 1: shifts past 6, 5, 4, 2 (4 shifts) to the front. Key = 3: shifts past 6, 5, 4 (3 shifts)
1 is the new minimum, so it needs the maximum possible number of shifts — all the way to the front. 3 needs 3 shifts, landing between 2 and 4.
Return: [1, 2, 3, 4, 5, 6] ✓ shift count varied wildly per element — that's insertion sort's input-sensitivity
Shift and insert
arr = [5, 2, 4, 6, 1, 3]
for i in range(1, len(arr)):
key = arr[i] # the element being inserted
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # shift right to make room
j -= 1
arr[j + 1] = key # drop the key into its found spot
print(arr)Complexity Notes
Frequently asked questions
How is insertion sort different from bubble sort — aren't both O(n²)?
Same worst-case time complexity, but different mechanics and different constant factors. Bubble sort repeatedly swaps adjacent pairs across the whole array every pass; insertion sort shifts elements to make room and places each key once it finds its spot, doing meaningfully fewer write operations on average — which is why it's generally considered faster than bubble sort in practice, despite the same Big O.
Why is insertion sort so fast on nearly-sorted data?
If most elements are already close to their correct position, the inner while loop exits almost immediately for most keys — very few shifts are needed. In the extreme case of fully-sorted input, no shifts happen at all, giving true O(n) performance, not just a constant-factor improvement.
Why do real sorting libraries (like Python's Timsort) use insertion sort at all?
For small sub-arrays (typically under ~64 elements), insertion sort's low overhead beats the overhead of recursive divide-and-conquer sorts like merge sort or quick sort. Timsort specifically switches to insertion sort once a chunk gets small enough, combining the strengths of both approaches.
Is insertion sort stable?
Yes — the shift condition is strictly arr[j] > key, so an equal element is never shifted past the key; the key is inserted immediately after it instead. Equal elements never cross each other, preserving their original relative order.
Watch each key find its spot in the growing sorted section
Paste insertion sort into LearnBug and see every shift and every insertion live.