I mentioned on twitter that I wrote a quick **insertion sort function in Python** using Pythonista on my iPad Pro. Searching and sorting algorithms are very popular subjects in my computer since and algorithms classes, so I am familiarizing myself with the more common ones and coding them up using Python and C#. I've already mentioned a couple of popular sorting algorithms in articles: selection sort and merge sort.

## Insertion Sort

Insertion Sort is O(n^{2}) and iterates through each item in the list, inserting each one in its proper location within the sorted items. Here is one solution to insertion sort in Python.

def insertion_sort(integers): """Sorts a list of integers in-place. :param list integers: List of integers to sort. :return: Nothing. Sorts in-place. :rtype: None >>> lst = [] >>> insertion_sort(lst) >>> assert(lst == []) >>> lst = [1] >>> insertion_sort(lst) >>> assert(lst == [1]) >>> lst = [1, 2] >>> insertion_sort(lst) >>> assert(lst == [1, 2]) >>> lst = [2, 1] >>> insertion_sort(lst) >>> assert(lst == [1, 2]) >>> lst = [5, 4, 3, 2, 1, 0] >>> insertion_sort(lst) >>> assert(lst == [0, 1, 2, 3, 4, 5]) >>> lst = [100, 84, 100, 16, 34, 34, 19, 0, 6, 100] >>> insertion_sort(lst) >>> assert(lst == [0, 6, 16, 19, 34, 34, 84, 100, 100, 100]) """ if len(integers) < 2: return for i in range(1, len(integers)): value = integers[i] j = i while j > -1: j -= 1 if value > integers[j]: break integers[j+1] = integers[j] integers[j+1] = value

The code for insertion sort is short. I just included several Doctests for the function.

If you are learning various computer science topics and algorithms, I hope you find the code useful!

I hope to see on you twitter. I am @KoderDojo

**Posted by David Hayden**