Can someone explain how recursive insertion sort works?

Question

Assuming A is an array, and n is the number of elements in A,

recursive_insertion_sort(A, n)
    IF n > 1 THEN
        recursive_insertion_sort(A, n-1)
        key = A[n]
        i = n - 1
        DOWHILE A[i] > key AND i > 0
            A[i+1] = A[i]
            i = i - 1
        ENDDO
        A[i+1] = temp
    ENDIF
END

Can someone explain how recursion works in this case? There are a few things I don't understand:

1. I don't understand why we have to call the function again if n > 1.
2. Why do we input (n-1) when we call the function again? Is it so that we start the entire process from n = 2, the first 2 elements?
3. How does recursion in general work? Like, once we call the function again, do we ignore the code from line 4 onwards, and jump straight into the second call? Or do we run the 2nd call in conjunction with the first call?

Musicale

Answer 1

Before discussing the implementation, let's explain what this function does: it does not sort the entire array A, but only its initial n elements. You can pass the length of the array for n to sort the whole thing, but the fact that you pass the length separately is essential to understanding the rest of the answer.

I don't understand why we have to call the function again if n > 1.

Perhaps a better way to explain the meaning of this condition would be that we do not call this function again when n is one or less. This is called the base case of recursive algorithm, i.e. the case when you don't have to do anything. In case of sorting it means that an array of only one element is already sorted.

Why do we input (n-1) when we call the function again?

Since n is the number of elements that we need to sort, We pass n-1 to sort the front of the array. Once the function returns, we know that the portion A[1..n-1] is already sorted. All we need to do is to move A[n] to its right place. We do that in the DOWHILE loop that follows: we go backward one element at a time, moving elements that are bigger than A[n] to the right. Once the loop is over, we place A[n] to its new place. Now the range A[1..n] is sorted.

How does recursion in general work?

The function has two cases - the trivial base case, when everything is done, and a reduction step, when you use recursive invocation to solve a simpler problem, and then use the results of the simpler solution to construct your final solution.

once we call the function again, do we ignore the code from line 4 onwards, and jump straight into the second call?

No, once the function returns, we continue where we left. In your case, the function waits for the A[1..n-1] range to be sorted before placing A[n] to the right place.

Pushing

Thanks for taking the time to help me and answering to all of my questions - I know I asked a lot of probably basic questions but I was really confused haha. I am able to understand the algorithm & recursion now. Thank you very much! :) – Musicale

Answer 2

Small example to understand how this works :

recursive_insertion_sort([1, 7, 5, 2], 4)
    | recursive_insertion_sort([1, 7, 5, 2], 3)
    |    | recursive_insertion_sort([1, 7, 5, 2], 2)
    |    |    | recursive_insertion_sort([1, 7, 5, 2], 1) 
    |    | puts 7 in the right position between it's ORDERED left values [1] -> [1,7]
    | puts 5 in the right position between it's ORDERED left values [1,7] -> [1,5,7]
puts 2 in the right position between it's ORDERED left values [1,5,7] -> [1,2,5,7]

Oshinski

I see. Writing it this way does help make it much clearer for me to understand. Thanks :) – Musicale

you're welcome, it is always helpful for me to write the call tree to understand a recursion – Oshinski