Skip to content
Insertion sort

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

6
3
8
2
5
01234
In order so farNot checked yet

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

Python

In 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 a

n 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.