Insertion Sort Using Python

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(n2) 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
Koder Dojo
David Hayden is a professional Microsoft web developer. He mentors and tutors computer science students in C, C++, Java, and Python. In addition to writing computer science and programming tutorials at Koder Dojo, he also writes tutorials on C#, ASP.NET Core, and Azure as well as tutorials on Orchard Core.