mastorna.it
IT

Sorting algorithms · 1/7

Insertion sort

Builds a sorted prefix one item at a time.

Average timeΘ(n²) SpaceΘ(1) StableYes In placeYes

How it works

Extract the current key, shift larger prefix values right, then insert the key into the gap.

Invariant: Before iteration i, A[0…i−1] contains the original prefix elements in sorted order.

Step-by-step visualization

Each bar represents one element. Colors identify compared elements, the pivot or key, the final region and the active range.

Use 2 to 16 values. This visualizer accepts values from 0 to 999.

Comparisons
0
Writes
0
Swaps
0
Pass / level
0
active comparison pivot / key final

Pseudocode linked to the visualization

  1. for i ← 1 to n − 1
  2. key ← A[i]
  3. 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

The highlighted line corresponds to the operation described by the visualizer. Index-management details are intentionally simplified.

Complexity analysis

Best caseΘ(n)

Already sorted: one comparison per key and no shifts, Θ(n).

Average caseΘ(n²)

A key crosses a linear fraction of the prefix on average, Θ(n²).

Worst caseΘ(n²)

Reverse order causes n(n−1)/2 shifts, Θ(n²).

Auxiliary spaceΘ(1)

Only a key and indices are stored: Θ(1). Strict > comparisons preserve stability.

Properties at a glance

Stable

Stability concerns the relative order of elements with equal keys.

In place

This classification refers to the version shown on this page.

When to use it and what to avoid

A good choice when…

Excellent for small or nearly sorted arrays and as the finishing stage in hybrids.

Common mistake

Using ≥ instead of > can reverse equal elements and lose stability.