Python Program for Insertion Sort

In this tutorial, you will learn how selection sort work and how to perform selection sort with example.

An array is partitioned into a "sorted" sub-array and an "unsorted" sub-array. while starting, the sorted sub-array contains only the first element of our original array. The first element in the unsorted array is evaluated so that we can insert it into its proper place in the sorted sub-array. The insertion is done by moving all elements larger than the new element one position to the right. This process works till sort completion.

Example :

    
# python program to sort array using insertion sort
def insertion_sort(arr):
    for i in range(1, len(arr)):
        for j in range(i - 1, -1, -1):
            if(arr[j] > arr[j + 1]):
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

arr = [10,4,3,9,8,2,5,6]

print("Before Sorted :: ",arr)
print("After Sorted :: ",insertion_sort(arr))
       

Output :

    
Before Sorted ::  [10, 4, 3, 9, 8, 2, 5, 6]
After Sorted ::  [2, 3, 4, 5, 6, 8, 9, 10]
    

The worst-case time complexity of insertion sort is O(n²), where n is the size of the input. The worst case happens when the array is reverse sorted. The best-case time complexity of insertion sort is O(n). The best case happens when the array is already sorted.