Insertion sort builds a sorted prefix one element at a time.

At each step, take the next element and move it left until it reaches its correct position among the elements already processed.

The key invariant is:

before each iteration, the prefix already processed is sorted and contains exactly the same elements as before.

If an element may move across most of the prefix, the worst-case running time is

$$O(n^2).$$

When the input is already or nearly sorted, however, few shifts are needed and insertion sort can be efficient in practice.

Insertion sort is stable when equal elements are not moved past one another, and it can be implemented in place. Its value is not only as a sorting method: it is a simple example of an incremental algorithm maintained by an invariant.