Home » Python » Python Programs

Python Program for Insertion Sort

Insertion Sort in Python: In this tutorial, we will learn about the insertion sort, its implementation, how to implement insertion sort in an array or list in Python. By Soumya Sinha Last updated : April 21, 2023

What is Insertion Sort?

Insertion sort is a sorting algorithm that works similarly as we sort playing cards in our hands. The input list is divided into two parts: one is a sorted sublist and the other one is an unsorted sublist. Elements from the unsorted sublist are picked up and placed at their correct suitable position.

This algorithm is almost similar to that of selection sort. The only difference is that in selection sort in each iteration we search for the smallest element in the unsorted sublist and swap it with the first element of the unsorted sublist. But in the case of insertion sort, we pick the first element of the unsorted sublist and place it in its correct final position i.e. we sort the first i elements in each iteration of the outer loop.

Here in this algorithm, the input list is divided into two parts (similar to that of selection sort)

• A sorted sublist (built from left to right) of elements starts at the left end of the list.
• An unsorted sublist of elements occupies the rest of the list.
  In each iteration, the algorithm will place an unsorted element in its correct position.

Procedure for Insertion Sort

The procedure of insertion sort is as follow,

Insertion_Sort(arr):
   n =len(arr)
   For i=1 to n:
       key = arr[i]
       j=i-1 
       while j >= 0 and key < arr[j]:
           arr[j + 1] = arr[j]
           Decrement j by 1
       arr[j+1] = key

Insertion Sort Example

Consider an array < 12, 41, 76, 17, 25>.

Initially key = arr[1] = 41. Now we will compare the elements which are present to the left of the key. For each and every element which is greater than the key place it just behind the element smaller than it.

As 41 > 21 we won't make any changes here.

<12, 41, 76, 17, 25>

Now key = arr[2] = 76. We will again repeat the same process but this time we won't make any changes as the elements are already placed at their correct position.

<12, 41, 76, 17,25>

Now key = arr[3] = 17.We will again repeat the same process and this time the element 17 needs to be placed in its correct position at index 1 so we will shift the elements one by one to make space.

<12, 41, 76, 76, 25> (for j = 2)

<12, 41, 41, 76, 25> ( for j= 1)

Now place the key in its correct position.

<12, 17, 41, 76, 25>

Repeat the above step for the last element 25 to obtain the sorted list.

key = arr[4] = 25.

<12, 17, 41, 76, 76>

<12, 17, 41, 41, 76>

Now place the key in its correct position.

<12, 17, 25, 41, 76>

We can see that after each iteration first i+1 element is in sorted order.

Time Complexity: O(n^2)

Python program to implement insertion Sort

import sys

def insertion_sort(arr):
    # This function will sort the array in non-decreasing order. 
    n = len(arr)
    # After each iteration first i+1 elements are in sorted order.
    for i in range(1, n):
        key = arr[i]
        j = i-1
        # In each iteration shift the elements of arr[0..i-1], 
        # that are greater than key, to one position ahead 
        # of their current position 
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1 

        arr[j+1] = key
        
    return arr

# main code
if __name__=='__main__':

    arr = [24, 17, 66, 33, 72, 47, 68, 41, 105, 30]
    print("Sorted array: ")
    print(insertion_sort(arr))

Output

Sorted array: 
[17, 24, 30, 33, 41, 47, 66, 68, 72, 105]

Python Data Structure Programs »

---