Sorting

Insertion Sort

A simple, stable sorting algorithm that builds a sorted prefix one element at a time.

Insertion sort is often explained with a familiar mental model: sorting playing cards in your hand. You take the next card, compare it to the cards already arranged, shift larger ones to the right, and insert the new card into the correct position.

This makes insertion sort one of the best beginner-friendly sorting algorithms. It is easy to follow visually, works well on small datasets, and performs especially well when the input is already nearly sorted.

Watch Visualization View Pseudocode

Quick Facts

Main Idea

Keep the left side of the array sorted, then insert the next element into its correct place.

Key Operation

Shift larger elements to the right to make space for the current value.

Space Usage

Insertion sort is in-place, using only O(1) extra space.

Where It Shines

It performs well on small inputs and nearly sorted arrays.

Key Idea

Insertion sort does not sort the whole array at once. Instead, it grows a sorted prefix from left to right.

At each step, the next element becomes the key. The algorithm shifts any larger values one position to the right, then inserts the key into the gap that remains.

Visualization

This visualization highlights the sorted prefix, the current key, the shift operations that make space, and the final insert step.

How It Works

Start Sorted Prefix

Treat the first element as a sorted subarray of length one.

Pick the Key

Take the next element in the array and call it the key.

Shift Larger Values

Move elements in the sorted prefix one position to the right while they are larger than the key.

Insert the Key

Place the key into the empty spot so the prefix stays sorted.

Why It Matters

Beginner Friendly

Insertion sort is one of the clearest algorithms for introducing sorting logic and loop control.

Great Mental Model

The “cards in your hand” analogy makes the algorithm intuitive before students even write code.

Practical on Small Inputs

Many faster real-world algorithms still use insertion sort for very small subproblems.

Nearly Sorted Data

When the array is already close to sorted, insertion sort can be very efficient.

Pseudocode

This pseudocode shows the full insertion sort process:

for i from 1 to n - 1:
    key = A[i]
    j = i - 1

    while j >= 0 and A[j] > key:
        A[j + 1] = A[j]
        j = j - 1

    A[j + 1] = key

The important detail is that the key is saved first, then larger values are shifted, and finally the key is inserted into the correct position.

Performance

Time Complexity

Best case: O(n)
Average case: O(n²)
Worst case: O(n²)

Space & Stability

Extra space: O(1)
In-place: Yes
Stable: Yes

Insertion sort is not the fastest general-purpose sort for large random inputs, but it is extremely useful for teaching and for small or nearly sorted data.

Common Mistakes

Not Saving the Key

If you start shifting values before storing the key, you can lose the value you were trying to insert.

Off-by-One Errors

Many learners make mistakes when moving left through the sorted prefix or placing the key back at j + 1.

Breaking Stability

Using >= instead of > can change the order of equal elements and break stability.

Confusing Swap vs Shift

Insertion sort is mainly about shifting larger values, not repeatedly swapping neighbors.

Outcome

After this lesson, learners should be able to explain the idea of a sorted prefix, describe the role of the key, trace the shift-and-insert process, and read or write basic insertion sort pseudocode correctly.

Back to Home