Program for Insertion sort (Recursive way) using Python

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

Program for Insertion sort (Recursive way) using Python

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.

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.