Insertion Sort using Python

Insertion sort is a sorting algorithm that sorts the elements one at a time. The average time complexity of the algorithm is O(n²). This algorithm is also called a linear sort algorithm and we’ll understand how the algorithm works by manually sorting the list [2, 5, 1, 7, 4] before implementing the same in python.

1.Consider the list arr as [2, 5, 1, 7, 4]
2. We do not change the first element and we start sorting from the second element.
3. Since the second element is greater than 2, the position does not change. arr = [2, 5, 1, 7, 4]
4. Now the third element is 1, we keep checking from the left and since it is less than 2, we place 1 before 2 and move all the elements in one position to the right. arr = [1, 2, 5, 7, 4]
5. The next element to be sorted is 7 and since all the elements before that are less than it, we do not change the position of any elements.
arr = [1, 2, 5, 7, 4]
6. The last element to sorted is 4. From the left, it is greater than 1, and 2 but less than 5. Hence, the value is placed between 2 and 5. arr = [1, 2, 4, 5, 7]

The below python code is the implementation of the insertion sort algorithm.

import random
def insertion_sort(arr):
  for i in range(1, len(arr)):
    anchor = arr[i]
    j = i - 1
    while j >= 0 and anchor < arr[j]:
      arr[j + 1] = arr[j]
      j = j - 1
    arr[j + 1] = anchor
  return arr
arr = []
for _ in range(100):
  arr.append(random.randint(1, 500))
print(insertion_sort(arr))

Thank you for reading this article and I hope you have understood how the insertion sort algorithm works. Keep Learning :)