algoquest.
Sorting · 20 min · Beginner-friendly

Insertion sort.
One step at a time.

Insertion sort: Put each number in its place, just like sorting a hand of cards.

By the end, you can…
  • Follow the sorted prefix as it grows
  • Explain a key, a comparison, and a shift
  • Predict the next action in an insertion-sort trace
  • Explain when insertion sort is a useful choice
Before you start

Read an array from left to right; indices start at 0.

New words? The examples below explain each one.

01 / Learn the idea

Think of a hand of cards

Imagine picking up cards one at a time. Keep the cards in your hand sorted. When a new card arrives, slide larger cards right until there is space to insert it. Insertion sort does the same thing with an array of values.

Work through it

With [4, 2, 3], begin with [4] as the sorted prefix. Hold 2, shift 4 right, then insert 2: [2, 4, 3]. Next hold 3, shift 4, compare 2 with 3, and insert 3: [2, 3, 4].

  • Array: an ordered collection accessed by index
  • Key: the value currently held for insertion
  • Shift: move a larger value one position to the right

One promise, every pass

Before each pass, the prefix to the left of the next key is already sorted. Inserting that key in the right place grows the sorted prefix by one. This repeated promise is called a loop invariant. The prefix is sorted internally, but its values may still move when a smaller key arrives later.

Work through it

In [2, 4, 3], the prefix [2, 4] is sorted. It is not the final order: 4 will move right so 3 can fit between 2 and 4.

  • Sorted prefix: a sorted region at the start of the array
  • Loop invariant: a condition that stays true between loop iterations
  • Stable: equal values keep their original relative order
02 / Watch, then try

Make the next step make sense.

Start with Next to inspect one action at a time. Try a new input and watch the same rules work on different values.

Up to 32 safe integers, separated by commas. Negative numbers and duplicates work too. Leave blank to try an empty array.

Or try:
Inside the algorithmStep 1 of 26
Prefix4index 0
Waiting2index 1
Waiting7index 2
Waiting3index 3
Waiting1index 4
Held key—No key held outside the array.
start

Begin with the first value as a sorted prefix. The rest will be inserted one key at a time.

0Value comparisons
0Rightward shifts
1Sorted prefix length

Previous and Next pause playback. Reset keeps your input. Play starts only when you choose it.

Follow the pseudocode
  1. start with the first value as a sorted prefix — current action
  2. for i = 1 to n − 1:
  3. key = A[i]; j = i − 1
  4. while j ≥ 0 and A[j] > key:
  5. A[j + 1] = A[j]
  6. j = j − 1
  7. A[j + 1] = key
  8. return A
Look at the raw array storage

[4, 2, 7, 3, 1]

A shift copies a value right; it does not erase its old slot. The gap marks the slot we can overwrite. The held key preserves the value that belongs there.

03 / Try a challenge

You call the next move.

Use the ideas you’ve learned to predict what happens next.

Case 1 of 30 / 6 points

2 points on your first correct try without a hint; 1 after a hint or retry. Take your time. Scores are not saved yet.

Compare4index 0
Gap·index 1
Waiting3index 2
Held key2Safe here while the gap moves.
We compared 4 with key 2. Which action comes next?
04 / Check your understanding

What’s clicking?

6 questions. Clear explanations. As many tries as you need.

0 of 6 checked · 0 correct. Answers stay on this page only.

Question 1What is the key in insertion sort?
Question 2The sorted prefix is [2, 7] and the key is 4. What happens to 7?
Question 3Does a value in the sorted prefix always stay at its current index?
Question 4For an already sorted array, how does the number of value comparisons grow?
Question 5Why do we shift only when a value is strictly greater than the key?
Question 6Which input usually makes insertion sort do the most shifting?
05 / Go a little deeper

The work behind the steps.

Best caseO(n)

Already sorted: one comparison per key, no shifts.

Average & worst caseO(n²)

Disordered values may shift across the growing prefix.

Auxiliary spaceO(1)

For the in-place algorithm: hold one key and a few indices.

Count actions, not milliseconds

One value-to-key comparison counts as one comparison, whether its answer is true or false. A rightward copy counts as one shift. Loop checks and the final key write are not included. These counts explain the work; they are not timing benchmarks.

Why the algorithm works

The prefix starts sorted with at most one value. Each pass inserts the next key in order and grows that prefix by one. When every value is in the prefix, the whole array is sorted. Comparing with >, rather than ≥, leaves equal values in their original relative order: the sort is stable.

When would you choose it?

  • Simple, stable, and useful for small or nearly sorted inputs
  • Many shifts on large, disordered inputs
  • This teaching tool stores snapshots, so its memory use exceeds that of the in-place algorithm

The teaching tool has its own cost

This player copies the input and stores a full array snapshot for every event so you can rewind. With O(n) events in the best case and O(n²) in the worst, copying n values per event gives O(n²) best-case and O(n³) worst-case trace-generation time and stored space. That is different from the O(1) auxiliary space of the underlying in-place sort. Inputs are capped at 32 values, at most 1,056 snapshots.

Try the edge cases

Empty and one-value arrays; Repeated values; Negative integers; Already sorted and reverse-sorted arrays. What changes in the comparison and shift counts?

One idea, understood.

You’ve explored insertion sort. Revisit the examples, experiment with a new input, or return to the learning path.

Back to the path ↗