Insertion Sort

Insertion Sort is a simple sorting algorithm. It is like picking up an element from the list and inserting it to its rightful index as per intended order of the elements in the list. Initially, the first element is considered to be at its right place and as we go through the elements of the list, the sorting takes place by comparing the elements.

Illustration:

for all elements in list,step=from step=0 to step=length(list)-1
    first element is sorted,when step=0
    key=list[step],the element to be extracted to insert at the right index
    j=step-1
    while j>=0 and key < value at index j
        list[j+1]=list[j]
        j=j-1
    list[j+1]=key

Time Complexity:

• Worst Case: O(n2)
• Average Case: O(n2)

• Best Case: O(n) Space Complexity: O(1)

  Program for insertion sort:

  def insertionSort(data):
  
    for step in range(0, len(data)):
        key = data[step]
        j = step - 1
  
        while j >= 0 and key < data[j]:   # Change key<data[j] to key>data[j] for descending order.        
            data[j + 1] = data[j]
            j = j - 1
  
        data[j + 1] = key
        print("step",step," -- ",data)
  inp=input("Enter the data: ").split()
  data=[]
  for i in inp:
    data.append(int(i))
  insertionSort(data)
  print('Sorted list in Ascending Order:')
  print(data)
  

Output: