Insertion Sort

Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: simplicity of implementation, efficient for very small data sets or sets that are substantially sorted, uses constant memory, and is stable.

Performance:
- Best: O(n)
- Average: O(n^2)
- Worst: O(n^2)

Wikipedia link: http://en.wikipedia.org/wiki/Insertion_sort