12.1.6. Recursion Analysis

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.

In this chunk, we are explaining how insertion sort can be approached recursively. In a recursive approach, the array is divided into two parts: a sorted part and an unsorted part. The sorting process starts with a single element already considered sorted. We take the next unsorted element and find its correct position in the sorted part. We then recursively apply the same logic to the remaining unsorted part of the array until all elements are sorted. This means that every time we call the recursive function, we solve a slightly smaller problem.

Imagine a librarian sorting a set of new books on a shelf. The librarian first places the first book on the shelf, which is now a one-book sorted section. Each new book is examined individually, and the librarian finds the correct place for it among the already sorted books. This continues until all new books are on the shelf in the correct order. Just like the librarian, the recursive insertion sort systematically builds up a sorted collection from an unsorted batch.

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, we break down the recursive formulation of insertion sort. The function works by sorting from the start index to the end of the array. If the start index reaches 'n minus 1', this means there's nothing left to sort, so the function returns. Otherwise, it takes the element at the start index and finds its correct position among the already sorted elements by inserting it. This is followed by a recursive call to sort the remainder of the array, starting from the next index after the current start position.

Think of this process like gradually building a house. First, you start with a solid foundation (the first element). As you build (add new elements), you ensure that each level of the house is in the correct order before moving on to the next level. If the most recent addition fits perfectly, you simply move on without any adjustments. If it doesn’t fit, you make space and adjust until it does. Just like constructing layers of a house, the recursive insertion sort method incrementally builds up the sorted array.

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, it takes time t n to sort the entire thing. This breaks of it taking time t n minus 1 to sort the first part up to n minus 2, and then n minus 1 step to the insert right. So, we get same recurrence as we did for selection sort t of n is t of n minus 1 which is the recursive phase.

This section discusses the time complexity of the recursive insertion sort algorithm. The time complexity for sorting the array segment is represented by 't(n)'. To sort the complete array from index 0 to n-1, the algorithm first sorts the segment up to n-2, requiring 't(n-1)' for this operation. Additionally, it includes the linear time needed to insert the last element into the correct position, which takes 'n-1' steps. This results in a recurrence relation that mirrors the time complexity established for the selection sort.

Think of this like filling a bucket with water. Each time you want to fill it more, you have to handle the amount already there. You pour until it's full, requiring maximum effort each time (the 'insertion'). As the bucket fills (the recursion), the amount you can add gets smaller and smaller, but you still have to consider how full it is each time. The work required to add water changes based on how full the bucket is at any given moment, which is similar to recursion in sorting.

And if we expand this out exactly as we did before, we get n minus 1 plus n minus 2 down to n, which is n into n minus 1 by 2, which is order n square.

In this chunk, we analyze how the recursive insertion sort mirrors the iterative approach in terms of time complexity. By expanding the time calculations, we can see that the summation results in a quadratic time complexity, specifically 'n(n-1)/2'. This indicates that both the recursive and iterative methods for insertion sort will take similar amounts of time, roughly proportional to the square of the number of elements being sorted.

This concept can be visualized like a race. Regardless of whether a runner chooses to jog slower (recursive) or sprint faster (iterative), both runners will end up completing the same distance (sorting all numbers) in a similar amount of time, depending on their stamina (complexity) relative to the distance (size of the array).

--