Insertion sort.
- Time (worst)
- O(n²)
- Space
- O(1)
Take the next number. Make room. Put it in the right place.
Why learn insertion sort?
Insertion sort builds a sorted section from left to right. Take the next number, move bigger numbers one position right, and put your number into the space left behind. It can work well when a list is small or nearly sorted.
Customize input
Smallest → biggest
0 comparisons · 0 shifts
Start
Put each number where it belongs
Start with 6. Now take 3 and find where it belongs: before or after 6? Then do the same with each number that comes next.
Take a number → move bigger numbers right → put it back
Use Next for one action, or Play to watch. Drag the timeline to preview silently.
Voice is unavailable in this browser. Follow the explanations above.
Follow the logic
PythonIn Python, key is the number held above the list. j is the position we compare with it. The small labels below the boxes are positions, starting at 0.
def insertion_sort(a): for i in range(1, len(a)): key = a[i] j = i - 1 while j >= 0 and a[j] > key: a[j + 1] = a[j] j -= 1 a[j + 1] = key return an is the number of items. Best-case time: O(n) for an already sorted list. Average and worst-case time: O(n²). Extra space: O(1). Equal numbers keep their original order because we only shift strictly bigger numbers. Comparisons count number-to-key checks. The gap represents the next write position; Python keeps key separately and copies values during shifts. Playback stores extra snapshots for rewinding.

