Sorting Algorithm

Insertion Sort

“The Human Approach”

Time: O(n²)

Space: O(1)

History

This is the algorithm most humans run naturally. If you pick up a messy stack of papers and try to organize them by date, you are likely running Insertion Sort.

Because it mimics natural behavior, it is surprisingly efficient on data that is "natural"—meaning data that is already partially sorted. It serves as the backbone for complex modern algorithms like Timsort (used in V8 and Python).

How It Works

Insertion Sort builds the final sorted array one item at a time. It takes the next element and "inserts" it into the correct spot among the items you've already processed.

The Algorithm Step-by-Step

Pick: Take the first element from the unsorted section. Call it the "Key".
Compare: Look at the elements in the sorted section (to the left).
Shift: If a sorted element is larger than your Key, slide it one space to the right.
Drop: Once you find a value smaller than your Key (or hit the start), drop the Key into the gap.
Repeat.

The Shifting Mechanism

Unlike Selection Sort which swaps, Insertion Sort *slides*. This is better for the CPU cache and requires fewer actual write operations when the data is nearly sorted.

Best CaseO(n)

The Superstar Scenario. If the list is sorted, it just looks at each item, nods, and moves on. No shifting required.

Worst CaseO(n²)

If the list is backwards, every new item has to slide all the way to the front.

Average CaseO(n²)

On random data, it's quadratic. But for small $n$ (under 20), it's often faster than Quick Sort due to lower overhead.

SpaceO(1)

In-place. Very memory friendly.

Code Walkthrough

Real implementations in multiple programming languages. Select a language to view idiomatic code.

1def insertion_sort(arr: list[int]) -> None:
2    """Sort array in-place using insertion sort."""
3    n = len(arr)
4
5    for i in range(1, n):
6        key = arr[i]
7        j = i - 1
8
9        # Shift elements greater than key to the right
10        while j >= 0 and arr[j] > key:
11            arr[j + 1] = arr[j]
12            j -= 1
13
14        # Insert key at correct position
15        arr[j + 1] = key

Python • .py

Real World Use Cases

1Small arrays (n < 50)
2Data that is being received in real-time (Online sorting)
3Finishing touches on 'almost sorted' data
4The base case for recursive sorts (Merge Sort / Quick Sort)

Key Insights

It is stable.
It is extremely fast for small or nearly-sorted datasets.
It is the standard fallback for high-performance recursive sorts.
It handles live data streams well.

When to Use

Use it if the array is small (under 50 items) or if you know the data is already mostly sorted. This is often the default 'base case' optimization for advanced developers.