How to Write a Python Insertion Sort

The Python insertion sort works like sorting game cards. To use the insertion sort, you create two lists: a sorted and unsorted list. You compare each item in the unsorted list until you sort that item. The insertion sort is a common standard algorithm in the Python language.

Have you ever sorted playing cards in your hand? That’s one way to think about the concept of Python insertion sort. When you need to sort a list with only a few elements, the insertion sort has your back.

Insertion sorts place an unsorted element in its correct place after each iteration in an array.

In this guide, we’re going to talk about what insertion sorts are and how they work. We’ll discuss how to implement an insertion sort in Python, with reference to an example, so you can get started with this sorting algorithm.

What is a Python Insertion Sort?

An insertion sort divides a list into two sublists: sorted and unsorted. It then compares each element in the unsorted list and continues to do so until each item in the list is sorted.

An insertion sort algorithm moves a sorted item into the sorted sublist and removes it from the unsorted sublist. Both sublists are part of the same array, but they distinguish whether an item is sorted.

You can think of insertion sorts like how you would sort a set of cards in your hand in a card game.

You’d move one-by-one through the list of cards and compare them with each other. The sorted cards would appear in the left of your hand. The unsorted cards would appear on the right until you sort them all.

How Do Python Insertion Sorts Work?

Let’s get down to business and sort an array using the insertion sort algorithm. Consider the following unsorted array:

In an insertion sort, the first element is considered sorted. The second element is stored in its own variable. We’ll call this variable current_number.

We need to compare current_number with the item at the first position in the array. If current_number is greater than the first element, it stays in the same place. Otherwise, current_number is moved to the front of the first element.

4 is not greater than 9, so these two elements swap places.

The first two elements in our list are sorted. Next, we change the value of current_number to the third item in the list and compare it with all the items on its left.

Our current_number becomes 3. We need to compare:

• Is 3 greater than 9? No, so 3 is inserted before 9.
• Is 3 greater than 4? No, so 3 is moved before 4.

Our list now looks like this:

This process repeats until the list is sorted. Our list only has one more set of comparisons to perform because it only contains four values. In the next iteration, 5 becomes current_number.

• Is 5 greater than 9? No, so 5 moves before 9.

be used tNo more comparisons are made because 5 is the last number in our sorted list. After this iteration, our array has been sorted:

It’s that simple! In our insertion sort, we always kept the sorted values at the left of the list. The unsorted values appeared at the right.

For each iteration in the list, we compared current_number to all the unsorted items. This process repeated until our list was sorted.

How to Write an Insertion Sort in Python

It’s all fine and well walking through the insertion sort on paper. Now it’s time to get into the nitty-gritty and implement an insertion sort in Python.

Write a Sorting Function

We’ll start by writing a Python function which performs our sort:

def sortNumbers(toSort):
	for number in range(1, len(toSort)):
		current_number = toSort[number]
		i = number - 1

		while i >= 0 and current_number < toSort[i]:
			toSort[i + 1] = toSort[i]
			i -= 1

		toSort[i + 1] = current_number

Let’s walk through how this works. In our sortNumbers function we create a Python for loop which loops through every number in the list. Then, we set the first element in the list as a sorted value by assigning it to the Python variable current_number.

We iterate through every item in the unsorted Python list (every item after current_number). Then, we compare current_number with each number on its left. After this happens, we set the value of current_number to be equal to the element after it in the list.

Write a Main Program

We’ve got to write a main program which executes our insertion sort:

numbers = [9, 4, 3, 5]
sortNumbers(numbers)

print(numbers)

Our code returns:

[3, 4, 5, 9]

Our list has been sorted in ascending order! Congratulations on getting this far.

Python Insertion Sorts: Descending Order

Insertion sorts can sort numbers in descending order. To accomplish this, you need to invert the “less than” (>) sign in the while loop and make it a greater than sign:

"Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"

Venus, Software Engineer at Rockbot

Find Your Bootcamp Match

while i >= 0 and current_number > toSort[i]:

This line of code, substituted in our above example, will sort the items in a list in reverse order.

When Should You Use an Insertion Sort?

Insertion sorts are best used when the data in a list is either nearly sorted, or when you are sorting a small list. There are more efficient algorithms that you can use to sort large lists. For instance, a merge sort or a quick sort is faster.

Insertion sorts are faster than bubble sorts.

Insertion sorts are useful to know about anyway. Knowing how to implement an insertion sort give you another type of sort you can use.

Insertion sorts are less complicated than some other sorting algorithms. Once you’ve learned how to write an insertion sort, you closer to learning about more complex sorts like merge sorts.

Python Insertion Sort: Complexity Analysis

Like all algorithms, it is important to take into consideration the best, worst, and average complexities. This will give us an insight into how effective the algorithm is at doing its job: in this case, sorting lists.

The worst case and average complexities are O(n2). This means that the algorithm will grow exponentially slower as you add more values to sort in your list.

The best case scenario is O(n). This happens when we run the algorithm on a sorted list. The algorithm checks that the items are sorted and then stops running.

You can learn more about how we represent algorithm complexity in our two-part series on Big O Notation.

Conclusion

Insertion sorts are like sorting a list of cards in your hand in a card game. You keep two lists: a list of sorted items and a list of items to sort. Then, you work your way through the list of unsorted items and shuffle their positions until they are all sorted.

Are you looking for more Python programming language resources? Check out our complete How to Learn Python guide. You’ll find top tips on how to learn Python and a list of online courses, books, and other resources.