12.1.5. Recursive Formulation

So, once again as we saw for selection sort. There is a natural way to think of insertion sort as a recursive thing. We sort part of the array, and then we insert an element into that to grow it. So, in this case we think of the array as being into components. So, we have a sorted portion, and an unsorted portion. So, what we do is, we take the first element here and insert it and then we recursively apply the algorithm to the rest of the unsorted portion. So, if a 0 to i minus 1. So, this is position i and this is position i minus 1. So, i minus 1 is the last sorted position, i is the first unsorted position. Then we insert a i into the sorted portion. And then we recursively sorted a i plus 1 onwards. And once again when i is the actually here, at n minus 1, then we do not have to do anything, so we can just trivially return.

This chunk explains the recursive nature of insertion sort. It starts by discussing how you can view the insertion sort algorithm as fundamentally recursive. Rather than iteratively inserting elements into a sorted sequence, you can approach the problem by sorting a portion of the array and then handling the remaining unsorted portion recursively. The idea is to take the first unsorted element and find its correct position within the already sorted portion, then call the function again to sort the remaining elements until the entire array is sorted. This process continues until there's no unsorted element left.

Imagine you’re organizing a set of cards. You start with one card (which is naturally sorted by itself). Each time you want to add a new card, you look for its rightful position among the already sorted cards, carefully inserting it to maintain order. When all cards are added, you realize that the last added card could also have been laid out directly in its place without disrupting the order of already sorted cards. The recursive method is like having a friend help you, where each time they sort what's on the table until everything is tidy!

So, now we have recursive formulation in two parts. So, we have insertion sort itself, which says sort the unsorted segment from start to n minus 1. So, if start is already in at n minus 1 return; otherwise insert the value at position start into the rest of a, which you will see if below. And then recursively sort the rest of the array from sort plus 1 onwards.

In this chunk, a clear algorithm breakdown is provided. The recursive function for insertion sort consists of checking if the current segment (from 'start' to 'n-1') is already sorted — if it is, it simply returns. If not, it takes the element at the 'start' position and tries to insert it correctly into the sorted segment preceding it. The function then calls itself to apply the same logic to the next segment of the array (i.e., from 'start+1' to 'n-1'). This repetitive self-calling function is what characterizes a recursive algorithm.

Think of a series of books you need to sort on a shelf. You start by placing the first book in its position. Then, each time you add another book, you make sure it goes in the right spot among the already sorted books. Once you place it, you again check through the books. Also, if you notice there are already no books left to be sorted (like the last book in the sequence), you stop working as everything is organized!

Once again this is just give you practice in looking at recursively algorithms and writing down the analysis. So, whenever we have a recursively algorithm we write a recurrence; that is, we write of formulation of t of n in terms of smaller values of t. So, let us try to analyze this recursively algorithm. So, if you want to sort a 0 to a n minus 1, then what we are doing is, we are recursively sorting this segment, and then inserting this value. ... So, again there is no different between time for the recursive and iterative version; except the one should keep in mind in general that, recursive calls are more expansive then iterative loops.

This chunk covers the time complexity analysis of the recursive approach to insertion sort. The approach systematically breaks down the problem into smaller parts. For each element that needs to be inserted, you’ll traverse through the sorted segment, leading you to a time complexity of O(n²). Even though the recursive calls can seem more expensive in terms of stack space and function calls, for insertion sort, the nature of the problem remains the same: the worst-case performance stays quadratic, similar to the iterative version.

Imagine solving a complex puzzle. Each time you fit a piece, you may need to rearrange the nearby pieces. This might seem time-consuming, but it’s important to keep the order. Counting how many times you need to check and rearrange pieces might take longer as you go along, reflecting the complexity of the recursion method in sorting as more pieces are added!

--