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