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...