Insertion Sort is a very commonly used sorting algorithm. In the best case (the data you are feeding it is almost sorted), it runs in linear time, O(n). But in the worst case (data is sorted in opposite order), its run time is quadratic, O(n^2).

Example! (See me if you weren't in class.)

Insertion Sort Demonsration I found on the web. Try the array "8 4 5 2 7 9 1". It gives you a very good picture of how insertion sort actually works.