Editor

Python Program for Insertion Sort

Intermediate · Searching and sorting

Insertion sort builds a sorted list one item at a time, the way many people sort playing cards in their hand. Each new number is taken from the unsorted part and slid left until it sits just after a smaller number. This program prints the list after each insertion.

Program

insertion_sort.py
numbers = [12, 11, 13, 5, 6]
print("Original list:", numbers)
for i in range(1, len(numbers)):
key = numbers[i] # the number to insert into the sorted left part
j = i - 1
# Shift larger numbers one place to the right
while j >= 0 and numbers[j] > key:
numbers[j + 1] = numbers[j]
j = j - 1
numbers[j + 1] = key # drop the number into the gap
print(f"After inserting {key}:", numbers)
print("Sorted list:", numbers)
Output
Original list: [12, 11, 13, 5, 6]
After inserting 11: [11, 12, 13, 5, 6]
After inserting 13: [11, 12, 13, 5, 6]
After inserting 5: [5, 11, 12, 13, 6]
After inserting 6: [5, 6, 11, 12, 13]
Sorted list: [5, 6, 11, 12, 13]

How it works

  1. The first number on its own counts as sorted, so the loop starts at index 1.
  2. key is the number being inserted into the sorted part on its left.
  3. The while loop shifts every larger number one place to the right, opening a gap.
  4. numbers[j + 1] = key puts the number into that gap.
  5. Inserting 13 moves nothing because it is already bigger than everything before it, which is why insertion sort is fast on lists that are almost sorted.

Another way to write it

Using bisect.insort()

Using bisect.insort()
import bisect
numbers = [12, 11, 13, 5, 6]
sorted_list = []
for num in numbers:
bisect.insort(sorted_list, num) # insert in the right place
print(f"After inserting {num}:", sorted_list)
Output
After inserting 12: [12]
After inserting 11: [11, 12]
After inserting 13: [11, 12, 13]
After inserting 5: [5, 11, 12, 13]
After inserting 6: [5, 6, 11, 12, 13]

bisect.insort() finds the right position with a binary search and inserts the number there, building a new sorted list.

Try it yourself

Sort a list of names alphabetically with the same program, for example ["Meera", "Arjun", "Zoya", "Kabir"].

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises