Introduction to Python Programming Cycle of Python Varibles and Datatypes in Python Input and Output in Python Operators in Python Precedence of Operators in Python Typecasting in Python If Else in Python Loops in Python Break, Continue and Pass in Python Functions in Python Default Arguments and Keyword Arguments in Python Strings in python Lists in Python Tuple in Python Dictionary in Python Sets in Python List Comprehension in Python Unpacking Sequences in Python Higher Order Functions in Python Lambda Functions in Python Sieve of Eratosthenes Algorithm in Python Linear Search in Python Binary Search in Python Selection Sort in Python Bubble Sort in Python Insertion Sort in Python Merge Sort in Python

Insertion Sort in Python

Sorting means arranging the elements of a sequence in either ascending or descending order. Insertion sort works by repeatedly picking an element from the unsorted portion of the array and then putting it at the right position in the sorted portion of the array.

Dry Run

Initially, we have an array of size 1, so it is already sorted. Then we add the second element and and compare it with the previous element to check whether the array is still sorted or not. If yes, we move to the next iteration. Otherwise, we keep on comparing the current element with the elements before it. If the previous element is greater than the current element we push it one step to the right. This process continues until we find an element that is smaller than the current element. Then we place the current element next to that element and then move on to the next iteration. Hence, at every step, the array expands by 1. This process continues for all the elements and the array gets sorted. 

arr= [1,5,3,8,7,2,6]

Pass 1, i=1 cur = arr[1] = 5 j = i-1 = 1

At j=1,arr[1] > cur, so arr remains [1,5,3,8,7,2,6]

Pass 2, i=2 cur = arr[2] = 3 j = i-1 = 1

At j=1, arr[1] > cur, so arr[1+1] = arr[1], arr becomes [1,5,5,8,7,2,6]
At j=0, arr[0] < cur, so arr[0+1] = cur = 3 arr becomes [1,3,5,8,7,2,6]

Pass 3, i=3 cur = arr[3] = 8 j = i-1 = 2

At j=2, arr[2] < cur arr remains [1,3,5,8,7,2,6]

Pass 4, i=4 cur = arr[4] = 7 j = i-1 = 3

At j=3, arr[3] > cur so arr[3+1] = arr[3], arr becomes [1,3,5,8,8,2,6]
At j=2, arr[2] < cur, so arr[2+1] = cur = 7 arr becomes [1,3,5,7,8,2,6]

Pass 5, i=5 cur = arr[5] = 2 j = i-1 = 4

At j=4, arr[4] > cur, arr[4+1] = arr[4], arr becomes [1,3,5,7,8,8,6]
At j=3, arr[3] > cur, arr[3+1] = arr[3], arr becomes [1,3,5,7,7,8,6]
At j=2, arr[2] > cur, arr[2+1] = arr[2], arr becomes [1,3,5,5,7,8,6]
At j=1, arr[1] > cur, arr[1+1] = arr[1], arr becomes [1,3,3,5,7,8,6]
At j=0, arr[0] < cur, so arr[0+1] = cur = 2, arr becomes [1,2,3,5,7,8,6]

Pass 6, i=6 cur = arr[6] = 6 j = i-1 = 5

At j=5, arr[5] > cur, so arr[5+1] = arr[5], arr becomes [1,2,3,5,7,8,8]
At j=4, arr[4] > cur, so arr[4+1] = arr[4], arr remains [1,2,3,5,7,7,8]
At j=3, arr[3] < cur, so arr[3+1] = cur = 6, arr becomes [1,2,3,5,6,7,8]

Final sorted array = [1,2,3,5,7,6,8]

Implementation


def insertion_sort(arr):
    for i in range(1,len(arr)):
        j=i-1
        cur=arr[i]

        while j>=0 and arr[j]>cur:
            arr[j+1]=arr[j]
            j-=1

        arr[j+1]=cur

    print(f"After pass {i}, arr = ",arr)
    print()

arr = [1,5,3,8,7,2,6]
print("Initial unsorted list = ",arr)
    
insertion_sort(arr)

print("Final sorted list = ",arr)
Output
Initial unsorted list =  [1, 5, 3, 8, 7, 2, 6] 

After pass 1, arr =  [1, 5, 3, 8, 7, 2, 6]

After pass 2, arr =  [1, 3, 5, 8, 7, 2, 6]

After pass 3, arr =  [1, 3, 5, 8, 7, 2, 6]

After pass 4, arr =  [1, 3, 5, 7, 8, 2, 6]

After pass 5, arr =  [1, 2, 3, 5, 7, 8, 6]

After pass 6, arr =  [1, 2, 3, 5, 6, 7, 8]

Final sorted list = [1, 2, 3, 5, 6, 7, 8]
Time Complexity : O(n2)
Space Complexity : O(1) no extra space used.

Time Complexity Analysis

Worst Case Complexity : O(n2)
No. of comparisons = O(n2)
No. of swaps = n = O(n)
Explanation : It occurs when the array is sorted in the reverse order.
Average Case Complexity : O(n2)
No. of comparisons = O(n2)
No. of swaps = O(n)
Explanation : It occurs when the array is neither in ascending nor descending order.
Best Case Complexity : O(n)
No. of comparisons = n = O(n)
No. of swaps = 0
Explanation : It occurs when the array is already sorted.

Advantages and Disadvantages

Advantages :
  1. Suitable to use when the array is almost sorted.
  2. No additional space required.
  3. It is a stable algorithm i.e. relative order of the same elements is not preserved.
Disadvantages :
  1. Takes O(n2) time to sort the elements. Hence, not very efficient to sort large data.