Python program for Recursive Insertion Sort

The method of defining something in terms of itself is referred to as the recursive method. In this tutorial, we will perform recursive insertion sort operation to sort an array.

Algorithm for Recursive Insertion Sort

We have already seen the insertion sort operation with the simple method and we have basic knowledge on how sorting is done but recursive insertion sort is different let's have a look at the Algorithm followed by the code:

1. Create a function insertion_sort()
2. Declare the function with two parameters
3. The first parameter will be the array
4. The second parameter will be the length
5. Iterate through element [1] to element [n-1]
6. Compare the element [i]
7. Put it at a suitable index in the array
8. The array is now sorted
9. Print the sorted array

Program

As discussed above in the algorithm, let us now dive into the programming part of the Recursive Insertion Sort operation influenced by the algorithm.

def insertion_sort(arr, Len):

    if Len <= 1:
        return
    insertion_sort(arr, Len - 1)
    end = arr[Len - 1]
    
    i = Len - 2
    while(i>=0 and arr[i] > end):

        arr[i+1] = arr[i]
        i = i - 1

    arr[i + 1] = end

array = [9, 1, 7, 3, 5]
print("The Original array is: ", array)

insertion_sort(array, len(array))
print("The Sorted array is :", array)

The Original array is: [9, 1, 7, 3, 5]
The Sorted array is : [1, 3, 5, 7, 9]

Conclusion

In this tutorial, we have performed an Insertion sorting operation in python programming to sort an array. The time complexity of recursive insertion sort is O(n) and the space complexity is O(1).