Insertion sort is a simple sorting algorithm efficient for small datasets and for partially sorted lists. It builds a sorted list (array) of elements.

Best case time complexity is linear: O(n)
Worst case and average case time complexities are quadratic: O($n^2$)

Following code is in Python2.7