# Implementing The Insertion Sort Algorithm in Python

This tutorial was built using Python 3.6

In this tutorial we are going to be taking a look at the insertion sorting algorithm and how it works as well as how you can implement this algorithm in the Python programming language.

# Insertion Sorting

So the insertion sorting algorithm is a well known sorting algorithm that can sort an unsorted array in a worst case time of `O(N^2)` time. It works by iterating through an array and sorting elements in a linear fashion.

• The algorithm starts at element `0` in an array and considers element sorted.
• It then looks at the first element to the right of our sorted array that just contains our `0` position element
• It then inserts this unsorted element in to it’s correct location.
• Our sorted array now has 2 elements
• The algorithm proceed to insert the next element into the correct position in our sorted array until the entire list has been sorted.

# Implementing it in Python

Implementing it in Python can be done like so:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 `````` ``````# Insertion Sort In Python # # Performance Complexity = O(n^2) # Space Complexity = O(n) def insertionSort(my_list): # for every element in our array for index in range(1, len(my_list)): current = my_list[index] position = index while position > 0 and my_list[position-1] > current: print("Swapped {} for {}".format(my_list[position], my_list[position-1])) my_list[position] = my_list[position-1] print(my_list) position -= 1 my_list[position] = current return my_list my_list = [8,2,1,3,5,4] print(insertionSort(my_list)) ``````

When executed this should give you the following output:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 `````` `````` \$ python3.6 insertionSort.py Swapped 2 for 8 [8, 8, 1, 3, 5, 4] Swapped 1 for 8 [2, 8, 8, 3, 5, 4] Swapped 8 for 2 [2, 2, 8, 3, 5, 4] Swapped 3 for 8 [1, 2, 8, 8, 5, 4] Swapped 5 for 8 [1, 2, 3, 8, 8, 4] Swapped 4 for 8 [1, 2, 3, 5, 8, 8] Swapped 8 for 5 [1, 2, 3, 5, 5, 8] [1, 2, 3, 4, 5, 8]``````

# Conclusion

If you found this tutorial useful or require further assistance then please let me know in the comments section below!