Insertion sort in Python

Introduction

Insertion sort is a simple in place (i.e no need for an auxiliary memory) sorting algorithm. It is an efficient algorithm for small data sets, specially for lists that are partially sorted.

  • For more information about how sorting works, you may refer to the following article
  • For more in depth information about insertion sort you may check the following loop invariant article

Insertion Sort Diagram

Insertion sort explained

Insertion sort is fairly easy to visualize (see the diagram above). Here is a summary of the steps:

  • Start with an unsorted list
  • The first element from the left is already sorted because it is a single element
  • Go to the second element and compare it with the first. If they are out of order then swap them
  • Go to the third then go back all the way to the left comparing it with the previous element. Do the swaps as necessary
  • Note that at any point in time, the list is split at position (i) into two sublists. The left side of (i) is sorted and the right side (including (i)) is not sorted
  • Pick the next element from the unsorted part and put it in the right position in the sorted part
  • The position that separates the sublists (i) goes from 1 (second element) to the end of the list
  • The element at position (j) that we need to put in the right place goes from wherever (i) is and goes down to the left all the way to its correct position
  • We keep shifting that number until it lands in the right position. We do that by swapping

Here is a cool video on youtube demonstrating insertion sort visually in Romanian folk dance

Running time

Insertion sort algorithm has two nested loops. The outer loop index (i) goes from 1 to (n) where (n) is the number of elements in the list. The inner loop index (j) goes from (i) down to wherever the next sorted item needs to be positioned. This is not perfectly (n) times however for large lists and in worst case scenarios it is practically (n) so in big O notation, the running time is O(n^2).

Here is a summary of insertion sort running time:

  • The best case scenario for insertion sort happens when the input list is already sorted. In this case the running time is linear O(n) because the inner loop has no effect
  • A worst case scenario can happen when the input list is sorted in reverse order. In this case, the running time is O(n^2) because the inner loop will shift the entire sorted sublist before inserting the next element in its correct position

For more information about running time of an algorithm, you may refer to the following article.

Insertion sort in python code

Here is an example insertion sort python algorithm

If you run the code snippet above, you should get the following output:

Thanks for reading. For questions or feedback, please use the comment section below.

Add a Comment

Your email address will not be published. Required fields are marked *