Python Program for Recursive Insertion Sort
Last Updated :
28 Aug, 2023
Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.
Python Program for Recursive Insertion Sort for Iterative algorithm for insertion sort
Algorithm
// Sort an arr[] of size n
insertionSort(arr, n)
Loop from i = 1 to n-1.
a) Pick element arr[i] and insert
it into sorted sequence arr[0..i-1]
Python
def insertionSortRecursive(arr, n):
if n <= 1:
return
insertionSortRecursive(arr, n - 1)
last = arr[n - 1]
j = n - 2
while (j >= 0 and arr[j] > last):
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = last
if __name__ == '__main__':
A = [-7, 11, 6, 0, -3, 5, 10, 2]
n = len(A)
insertionSortRecursive(A, n)
print(A)
|
Output
[-7, -3, 0, 2, 5, 6, 10, 11]
Time Complexity: O(n2)
Auxiliary Space: O(n)
Python Program for Recursive Insertion Sort Using a divide and conquer
Step by step approach:
1.Define a function called insertion_sort_recursive that takes an array arr as input.
2.Check if the length of the input array is less than or equal to 1. If it is, return the array as it is already sorted.
3.Find the midpoint of the array by dividing its length by 2 using integer division.
4.Recursively sort the left half of the array by calling insertion_sort_recursive with the left half of the input array as its argument.
5.Recursively sort the right half of the array by calling insertion_sort_recursive with the right half of the input array as its argument.
6.Merge the sorted left and right halves of the array into a new sorted array.
7.Initialize two indices i and j to 0 to keep track of the current positions in the left and right halves of the array, respectively.
8.While i is less than the length of the left half and j is less than the length of the right half, compare the values at the current positions in the left and right halves of the array.
9.If the value at the current position in the left half is less than the value at the current position in the right half, append the value at the current position in the left half to the sorted array and increment i.
10.If the value at the current position in the right half is less than or equal to the value at the current position in the left half, append the value at the current position in the right half to the sorted array and increment j.
11.If either i or j has reached the end of its respective half of the array, append the remaining elements of the other half to the sorted array.
12.Return the sorted array
Python3
def insertion_sort_recursive(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = insertion_sort_recursive(arr[:mid])
right_half = insertion_sort_recursive(arr[mid:])
i, j = 0, 0
sorted_arr = []
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
sorted_arr.append(left_half[i])
i += 1
else:
sorted_arr.append(right_half[j])
j += 1
sorted_arr += left_half[i:]
sorted_arr += right_half[j:]
return sorted_arr
arr = [5, 2, 4, 6, 1, 3]
sorted_arr = insertion_sort_recursive(arr)
print(sorted_arr)
|
Output
[1, 2, 3, 4, 5, 6]
Time complexity: O(n log n)
space complexity: O(n)
Please Login to comment...