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.