Introduction

In the previous article we understood how insertion sort work. Now we will discuss the recursive way to implement insertion sort in our program.

Program

def sort(ip_arr, length):
    if length <= 1:
        return
    sort(ip_arr, length - 1)
    end_ele = ip_arr[length - 1]
    j = length - 2
    while(j>=0 and ip_arr[j] > end_ele):
        ip_arr[j+1] = ip_arr[j]
        j = j - 1
    ip_arr[j + 1] = end_ele
       
ip_arr = [6, 5, 11, 101, 13]
print("The input array is: ", ip_arr)
sort(ip_arr, len(ip_arr))
print("The sorted array is :")
for i in range(len(ip_arr)):
    print(ip_arr[i])

Output

Explanation

Algorithm for Insertion sort:

1. Iterate through element[1] to element[n-1].
2. Compare element[i] and put it at suitable index in the array where, 1 <= I <= n-1.
3. Return the sorted array.