Master Insertion Sort and Implement it in Python

Understand the algorithm

Understand Insertion Sort in 6 Minutes

Insertion sort is an awesome algorithm that has some quite interesting use-cases due to it nature.

First understand the basics of it.

Consider the list of integers.

Insertion sort explained

The above list has 10 elements. Now if you only consider the list of the first element (number 3), then that part is actually sorted. If number 3 was the only number in the list, then it would be sorted.

Now consider the list of the first two elements.

Insertion sort explained

Then we have the list of two elements, 3 and 5. Here we are lucky, as this is still sorted.

Now for the next element, 1, we are a bit out of luck, because if we just added that element to part of the list (the green part), then it would not be sorted.

Insertion sort explained

If one was added, we would need to swap it down until it is on place. First swapping 1 with 5.

Insertion sort explained

Then swapping 1 with 3. Then we are having a ordered list again, that is a list of the 3 first elements (the green part of the list below).

Insertion sort explained

Hence, the process is to think of the first element as a list and realize it is ordered. Then insert one element at the time. For each element inserted, swap it down until it is on place.

Why is Insertion Sort great to know?

Well, first of all it is simple to understand. Second of all, it is easy to implement (see the code below). But that is not the exiting stuff.

Well, what is it?

It has some interesting use case. See.

  • If you were to keep an ordered list in memory as part of your program.
  • But it also had a twist.
  • Someone would keep coming with new numbers all the time, and still ask you to keep the list ordered.
  • Then the efficiency of keeping this list ordered is good.

Why?

Because if the list is ordered and you need to add another element, you just follow the above procedure.

The worst case run-time for a list of N element is O(N).

What is the catch?

Well, the performance of the algorithm is not good. That is, there are more efficient algorithms out there to sort N elements.

Let’s analyze.

For the first element you use 1 operation. The second element 2 operations. The third element 3 operations. Wait a minute, isn’t that this formula?

1 + 2 + 3 + 4 + … + N = N(N+1)/2

Which unfortunately gives a performance of O(N^2).

So why bother about this algorithm?

Well, because of the use-case explained above. That you can keep it ordered and with low cost insert an element into it.

The code

import random


def generate_random_list(n):
    # n is the length of the list
    my_list = []
    for i in range(n):
        my_list.append(random.randint(0, 4*n))
    return my_list


def insertion_sort(my_list):
    for i in range(1, len(my_list)):
        for j in range(i, 0, -1):
            if my_list[j] < my_list[j-1]:
                my_list[j], my_list[j-1] = my_list[j-1], my_list[j]
            else:
                break


def main():
    my_list = generate_random_list(20)
    print(my_list)
    insertion_sort(my_list)
    print(my_list)


if __name__ == "__main__":
    main()

The above code implements the algorithm (see only 7 lines of code) and tests it.

I hope you enjoyed.