Insertion sort

Sorting Visual walkthrough

At a glance

Insertion sort grows a sorted section of the array, one value at a time. It is easy to understand and useful for small or nearly sorted inputs.

Property	What to remember
Typical time	O(n²)
Extra memory	O(1)
Stable?	Yes, with the implementation shown
Good choice when	The input is small or nearly sorted

Watch it work

The bars show the values and their current positions. Use Next to inspect one action, or Play to follow the whole sequence. You can enter your own numbers and compare what happens with a nearly sorted or reversed list.

Interactive walkthrough0 / 0

Explanation modeChallengePracticeGuidedExplain each step yourself, then reveal the answer when ready.

What is happening?

Explain the current action in your own words.

Reveal explanation

Why are we doing this?

Why is this step necessary?

Reveal explanation

Coming next

Predict what will happen next.

Reveal explanation

Step

0

PreviousPlayNextResetShuffle

Comparisons 0Writes 0Events 0

Custom values (4 to 10 integers from 1 to 99)

Use values

Purple: compared or moved | Green: completed portion | Orange: active work area

What the colors mean

Purple marks comparisons or movement, orange shows the active part of the array, and green highlights sections that the visualizer has completed. The animation counts individual comparisons and assignments in its teaching model, not CPU instructions or elapsed time.

Approach explained step by step

1. Start with index 1. Treat the first item as a sorted range of one element.
2. Save the current value. Call it the key. Keeping the key temporarily prevents it from being lost while moving other items.
3. Scan left. Compare the key with the element immediately to its left.
4. Shift larger elements. Copy each larger element one position to the right, making an empty space for the key.
5. Insert the key. Stop at the beginning of the array or when you find an element no larger than the key.
6. Repeat. Grow the sorted prefix by one element on every outer iteration.

Trace a small input by hand

For [7, 3, 5], start with [7]. Insert 3 before 7 to get [3, 7, 5]. Then compare 5 with 7, shift 7, and place 5 after 3. The result is [3, 5, 7].

Implementations in C# and C++

C#

C# | InsertionSort.cs

static void InsertionSort(int[] values)
{
    for (int i = 1; i < values.Length; i++)
    {
        int key = values[i];
        int j = i - 1;

        while (j >= 0 && values[j] > key)
        {
            values[j + 1] = values[j];
            j--;
        }

        values[j + 1] = key;
    }
}

C++

C++ | InsertionSort.cpp

#include <vector>
void insertionSort(std::vector<int>& values) {
    for (std::size_t i = 1; i < values.size(); ++i) {
        int key = values[i];
        int j = static_cast<int>(i) - 1;
        while (j >= 0 && values[j] > key) {
            values[j + 1] = values[j];
            --j;
        }
        values[j + 1] = key;
    }
}

Try a mental trace

What happens if the input is already sorted? Count how many comparisons the inner loop performs.

Complexity and trade-offs

Measure	Cost	Reason
Best case	O(n)	Already sorted: one comparison per inserted key.
Average case	O(n²)	Elements typically move through a substantial part of the sorted prefix.
Worst case	O(n²)	Reverse order means every new key must move to the front.
Auxiliary space	O(1)	Sorting modifies the input array in place.
Stability	Stable	Equal values are not shifted past one another.

Insertion sort usually performs fewer operations on nearly sorted arrays. It is rarely a good standalone choice for large unsorted inputs because the number of comparisons and shifts can grow quadratically.

Common mistakes

• Shifting the key itself instead of storing it before moving elements.
• Forgetting j >= 0 before reading values[j].
• Using >= rather than > in the shift condition, which can break stability for equal keys.

What the sorted prefix guarantees

After each outer-loop iteration, the first i + 1 elements are sorted. This is the central invariant of insertion sort. The algorithm does not need the rest of the array to be ordered; it finds the correct place for the next element by shifting larger values to the right. That also explains why it can behave well on nearly sorted inputs.

When insertion sort makes sense

Insertion sort is simple, stable when implemented with strict comparison, and works in place. It is often useful for short arrays or small partitions within more sophisticated algorithms. It is usually not the best standalone choice for large random datasets because its comparisons and shifts may grow quadratically.

Think about duplicates

In the examples, the shift condition is values[j] > key rather than >=. That choice preserves the relative order of equal-valued items, which is what stability means. If you change it to >=, repeated values can swap their original order.

Further reading

↗External referenceInteractive Insertion sort referenceExplore another walkthrough of insertion sort.↗Related lessonBig O notationUnderstand how algorithmic work scales with input size.↗Related lessonTime complexityLearn how to estimate the number of operations an algorithm needs.

Compare the approaches

↗Hands-on exerciseCompare sorting approachesRun insertion sort and merge sort on the same values. Compare their steps and explain why their behavior differs.