Insertion sort

Insertion sort

The algorithm consists of $n-1$ iterations. At iterations $1 \leq i \leq n-1$, we sort the prefix of array $a$ of length $i+1$. That is, before iteration , the subarray is sorted, and after the -th iteration, the subarray will be sorted. To do this, it is enough to find the right place to put .