Insertion Sort

Task: Sort this array in ascending order

for (int i = 1; i < n; i++) {    int j = i;    while (j > 0 && a[j - 1] > a[j]) {        swap(a, j - 1, j);        j--;    }}

What you are watching

Insertion sort keeps the front of the array sorted and grows that region one value at a time, walking each new value backwards past everything larger than it until it reaches its place. Sorting 7, 3, 9, 2, 5 shows the range of the work: 9 stops after a single comparison because it is already larger than everything before it, while 2 has to walk past three values to reach the front. That is why insertion sort is linear on nearly sorted data and quadratic on reversed data.