Latest
Home » Insertion Sort algorithm in Python

# Insertion Sort algorithm in Python Hello everyone, welcome back to programminginpython.com. Here am going to tell you how to implement Insertion Sort Algorithm in Python. In the previous posts, I have said about Merge Sort, Selection Sort, and Bubble Sort, here I will show you Insertion Sort which is more efficient than Selection and Bubble sort techniques.

Insertion Sort is an in-place sorting algorithm. Here a sub-list is maintained which always sorted, as the iterations go on, the sorted sub-list grows until all the elements are sorted. In each iteration, an element in the main list(unsorted list) is picked and placed correctly in the sorted list by shifting elements to the right which are greater than the element picked from the unsorted sub-list.

You can also watch the video on YouTube here.

### July Promo - Limited Time Sale Limited time sale - 50% OFF Learn in-demand data and AI skills on the 17th of July

See the below animations, By Swfung8Own work, CC BY-SA 3.0, Link

### July Promo - Limited Time Sale Limited time sale - 50% OFF Learn in-demand data and AI skills on the 17th of July By Simpsons contributorOwn work, CC BY-SA 3.0, Link

#### Time Complexity Of Insertion Sort

 Best Case O(n2) Average Case O(n) Worst Case O(n2)

The Complete Python Bootcamp From Zero to Hero in Python – Enroll Now.
Udemy

#### Algorithm

Given a list L of n elements with values or records L0, L1, …, Ln-1.

1. Initially, L0 is the only element in the sorted sub-list.
2. Compare L1 with the elements in the sorted sub-list(initially L0 and L1), and place it in the correct position(shift all the elements in the sorted sub-list that is greater than the
value to be sorted)
3. Repeat the same step until Ln-1

#### Program

```__author__ = 'Avinash'

def insertion_sort(sort_list):
for i in range(1, len(sort_list)):
key = sort_list[i]
j = i - 1
while j >= 0 and key < sort_list[j]:
sort_list[j + 1] = sort_list[j]
j -= 1
sort_list[j + 1] = key
print('\nThe sorted list: \t', sort_list)
print('\n')

lst = []
size = int(input("\nEnter size of the list: \t"))

for i in range(size):
elements = int(input("Enter the element: \t"))
lst.append(elements)

insertion_sort(lst)```