Home I have to sort an array using insertion sort and using recursion (without loops)

Questions

I have to sort an array using insertion sort and using recursion (without loops)

December 13, 2021

I have to sort an array using insertion sort and using recursion without using loops. I have tried but it is not sorting anything. Here is my code:

def recursiveInsertionSort(array, i, j):
    n = len(array)
    if i < n:
        temp = array[i]
        j = i - 1
        if j >= 0 and array[j] > temp:
            array[j + 1] = array[j]
            recursiveInsertionSort(array, i, j - 1)
        array[j + 1] = temp
        recursiveInsertionSort(array, i + 1, j)
    return array

arr = [10, 8, 7, 50, 60, 3, 9, -1]
print(recursiveInsertionSort(arr, 1, 0))

Output is [10, 8, 7, 50, 60, 3, 9, -1] same as the given array. Expected output is [-1, 3, 7, 8, 9, 10, 50, 60] Can anyone help me to find where the problem is?

>Solution :

Honestly there are too many mistakes in your code for me to list off, but this works:

def recursiveInsertionSort(array, i, j):
    n = len(array)
    if i < n and j >= 0:
        if array[j] > array[j + 1]:
            temp = array[j + 1]
            array[j + 1] = array[j]
            array[j] = temp
        recursiveInsertionSort(array, i, j - 1)
    if j == 0:
        recursiveInsertionSort(array, i + 1, i)
    return array

arr = [10, 8, 7, 50, 60, 3, 9, -1]
print(recursiveInsertionSort(arr, 1, 0))

Output: