## Insertion sort

An **insertion sort** is a very simple algorithm that looks at an object in a collection and compares its key to the keys prior to itself. You can visualize this process as how many of us order a hand of playing cards, individually removing and inserting cards from left to right in ascending order.

For example, consider the case of ordering a collection in ascending order. An insertion sort algorithm will examine an object at index *i* and determine if it's key is lower in value or priority than the object at index *i - 1*. If so, the object at *i* is removed and inserted at *i - 1*. At this point, the function will repeat and continue to loop in this manner until the object key at *i - 1* is not lower than the object key at *i*.

Given the following set of values:

*S = {50, 25, 73, 21, 3}*

Our algorithm will begin examining the list at *i = 1*. We do this because at *i = 0*, *i - 1* is a non-existent value and would require special handling.

Since 25 is less than 50, it is removed and reinserted at *i...*