Insertion Sort algorithm explained in python with example

Insertion sort is an algorithm for sorting a list of numbers. The key idea of this algorithm is to divide the list into two portions: a sorted portion and an unsorted portion. At each step of the algorithm a number is moved from the unsorted portion to the sorted portion until the entire list is sorted. Make sure you watch the video tutorial given at the end to understand how the code is written.

Insertion sort implemented in python:

In the python code below we have a list containing 10 unsorted numbers to sort. In the first while loop we are iterating from the 2nd element so that the first element of the list becomes the first element of the sorted list. The first while loop selects an element from the unsorted list and the second while loop (nested inside first one) compares it with elements of the sorted list, if the selected element is less than the adjacent left element (sorted portion) then the left element is shifted into the current element’s place and the current element is copied into the left element’s place. The last while loop finally displays the sorted list.

list=[10,1,5,0,6,8,7,3,11,4]
i=1
while(i<10):
  element=list[i]  j=i
  i=i+1

  while(j>0 and list[j-1]>element):
    list[j]=list[j-1]    j=j-1

  list[j]=element

i=0
while(i<10):
  print (list[i])
  i=i+1

Time complexity: O(n²)

watch this video for understanding the algorithm, its implementation and time complexity.