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. Insertion Sort should be used when you have a small number of elements to sort or the elements in the initial collection are already "nearly sorted".

Performance: Best O(n), Average O(n^2), Worst O(n^2).

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