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

Question

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?

Answer 1

This one works for me,

def insertionSort(a, index):
    if index == len(a):
        return a
    else:
        if index > 0:
            for i in range(index, len(a)):
                temp = a[i]
                j = i - 1
                while j>=0 and a[j] > temp:
                    a[j+1] = a[j]
                    j -= 1
                a[j+1] = temp
        return insertionSort(a, index+1)

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