What am I missing here to complete the insertion sort of the array?

Question

I want to sort the array in ascending order using recursive insertion sort. This works until idx<len(arr) but the sorting isn't finished there. What am I missing?

Given is the code I wrote:

def insertionSort(arr, idx):
    i=idx
    if idx<len(arr):
        if arr[idx]<arr[idx-1]:
            arr[idx], arr[idx-1]=arr[idx-1], arr[idx]
        insertionSort(arr, idx + 1)
        
    return arr


print(insertionSort([3,4,1], 1))

The output is [3,1,4], but I want it to sort into [1,3,4]

https://stackoverflow.com/questions/12755568/how-does-python-insertion-sort-work — Nick, Aug 29 '22 at 09:18

score 0 · Answer 1 · answered Aug 29 '22 at 09:19

Your implementation is wrong. This would be a possible recursive implementation of Insertion Sort:

def insertionSort(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

And you call the function in this way:

insertionSort(arr, len(arr))

What am I missing here to complete the insertion sort of the array?

1 Answers1