Insertion sort is a sorting algorithm that maintains a sorted prefix of a list. At each step, the next element is removed from the unsorted suffix and inserted into its proper position in the prefix, shifting larger elements one place to the right.
For a list of 
elements, insertion sort uses 
comparisons and moves in the average and worst cases,
but only 
comparisons on an already sorted list. In big-O notation,
these bounds mean that the corresponding operation counts are bounded by constant
multiples of 
and 
,
respectively, for all sufficiently large 
. It is an in-place stable sorting algorithm and is effective
for small or nearly sorted inputs.
