Skip to content
BENIBIX Learn

Insertion Sort

Development🧮 Algorithms & Data StructuresSorting Algorithms

Also known as Insertion Sorting, Card Sort

Take each item in turn. Slide it back to its right place.

Think of it like

It is like sorting cards in your hand. You pick up one card at a time and slide it into place.

Example

A list of 20 scores is in order except for one new score at the end. Insertion sort fixes it in a few steps.

Why it matters

It is simple and quick on small or nearly sorted lists. Real sorting code uses it for that job.

Definition

Insertion sort builds a sorted part one item at a time. It takes the next item and slides it back until it sits in the right spot. On a list that is already nearly sorted, it is very fast. On a big jumbled list it is slow, about n squared steps. Fast sorts often switch to it for very small pieces.

Example code

python
def insertion_sort(a):
    for i in range(1, len(a)):
        x, j = a[i], i - 1
        while j >= 0 and a[j] > x:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x
    return a
Each item moves back past the bigger ones, then drops into its gap.
Insertion sort, on the left: each new card slides back into the sorted part.

Common mistake

Using it on a large, random list. Merge sort or quicksort will be far faster there.

Key takeaways

  1. 1
    Grows a sorted part. One item joins it each step.
  2. 2
    Great when nearly sorted. Few moves are needed.
  3. 3
    Slow on big messes. About n squared steps.

Compare