Insertion Sort Visualization & Step-by-Step Simulator

Q: What is the time complexity of insertion sort?

O(n) in the best case (already sorted), O(n²) in the average and worst cases. Space complexity is O(1).

About this visualization

Insertion sort builds a sorted list one item at a time, like sorting playing cards in your hand. It takes the next item (the key), shifts larger sorted items one place to the right and drops the key into the gap. It is very fast on small or nearly sorted lists.

How it works

The first item is a sorted list of one.
Take the next item (the key) and shift larger sorted items one place right.
Drop the key into the gap. Repeat until the list ends.

Worked example

Sort [12, 11, 13, 5, 6]. Key 11 shifts 12 right → [11, 12, 13, 5, 6]. Key 13 needs no shift. Key 5 shifts 13, 12 and 11 → [5, 11, 12, 13, 6]. Key 6 shifts 13, 12 and 11 → [5, 6, 11, 12, 13]. In total 7 shifts.

Enter these numbers in the simulator above to see every step.

Complexity and properties

Best case	$O(n)$
Average case	$O(n^{2})$
Worst case	$O(n^{2})$
Space	$O(1)$
Stable	Yes
In-place	Yes

Excellent on nearly sorted data.

When to use it

Sorting small arrays or almost-sorted data efficiently.
Understanding why insertion sort is used inside hybrid sorts like Timsort.
Counting shifts and comparisons for homework.

Frequently asked questions

What is the time complexity of insertion sort?

$O(n)$ in the best case (already sorted), $O(n^{2})$ in the average and worst cases. Space complexity is $O(1)$ .

Is insertion sort stable?

Yes. It only shifts items that are strictly greater than the key.

When is insertion sort better than quick sort?

For very small or nearly sorted inputs, where its low overhead and $O(n)$ best case win.