Insertion Sort

Builds a sorted prefix one element at a time, shifting larger elements right to open a slot for each key.