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.

Author

  • Barry Allen

    A Full Stack Developer with 10+ years of experience in different domain including SAP, Blockchain, AI and Web Development.

    View all posts

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

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