Insertion Sort

Insertion Sort builds a sorted prefix and inserts the next element in the correct position (shifting).

Best case with already sorted data: $O(n)$. Worst case $O(n^{2})$. Stable and good for small or nearly sorted arrays.

Nearly sorted data, small n, inner loop of hybrid sorters (TimSort uses Insertion Sort on runs). Therefore, Insertion Sort remains practically relevant.

Depth

Insertion Sort maintains an already sorted prefix. The next element is temporarily stored, larger prefix elements are shifted to the right, and the created gap takes in the element. After each round, the prefix has grown by one position and remains sorted.

The work closely corresponds to the number of inverse pairs, that is, the pairs that are out of order relative to the target order. Nearly sorted data thus create few shifts. Strongly reversed order, on the other hand, leads to a long shift chain per round.

Difficulty levels

1. Insert an element into a sorted prefix.
2. Connect shifts with the number of inversions.
3. Maintain stability through the exact comparison condition.

Pitfalls

If equal elements are shifted as well, the order of equivalent records may change. Often the temporarily stored element is also lost if overwritten directly in the array.