Step 1 of 6

Insertion sort

Insertion sort grows a sorted prefix: take the next element and shift larger ones right until its spot opens up. Like sorting cards in your hand.

O(n²) in general, but O(n) on data that's already almost sorted.
Stable (equal elements keep their order) and in-place.
Fastest of all for tiny arrays. Real std::sort implementations switch to it for ranges below about 16 elements.

for i in 1..n-1:
    key = v[i]; j = i - 1
    while j >= 0 and v[j] > key: v[j + 1] = v[j]; j--
    v[j + 1] = key

Your turn: implement insertion_sort and return how many element shifts it performed (a measure of how unsorted the input was).