23.2. Insertion Sort Example

So, here is a very simple way of describing insertion sort. So, if I want to sort n elements, then the way insertion sort does is that of course, there is nothing to sort the base case, then we have done. Otherwise, we look at the rest of the list starting from the second element and we recursively sort it and then we insert the first element into the sorted list.

Insertion sort is a method of sorting where we take an unsorted list and build a sorted list one element at a time. Initially, we consider the first element to be sorted. For each subsequent element, we compare it to the elements in the sorted list and insert it at the appropriate position. If the list is empty, we have nothing to sort, which is the base case. Otherwise, we proceed to sort the rest of the list recursively.

Think of insertion sort like sorting a hand of playing cards. You start with one card (which is already sorted), and you pick another card from the deck. You compare it with the cards in your hand and place it in the right position among them. This process continues until all cards are sorted.

So, the insertion sort apply to X 1 to X n, requires us to insert the value X 1 in the recursively sort to X 2 to X n. So, again we are applying the same function that we are trying to define to a smaller input and in the base case, the smallest input namely the empty one, we have an answer which is readily available for us.

In the context of insertion sort, the base case is when we have an empty array or a single-element array since there is nothing to sort in these cases. For a non-empty list of elements (X1 to Xn), we recursively sort the remaining part (X2 to Xn) and then insert X1 in the correct position of the sorted portion. This creates a smaller problem, allowing use of the same insertion sort method.

Imagine sorting names using index cards. If you have just one card (or no cards), you don’t have to do any sorting. When you add more cards, you simply place each new card in the right position among the already sorted cards, as if you were always focusing on inserting that card into a smaller sorted list.

One of the attractions of having inductive definitions is that they yield in a very natural way recursive programs. So, we do not have to think much, we can almost take the inductive definition and directly translate it as a program.

Inductive definitions lend themselves easily to recursion; they allow us to define a function in terms of itself with smaller inputs. For insertion sort, we can define the sorting process and then translate that definition into a recursive program without complication. This means we can focus on understanding the algorithm's logic rather than getting bogged down in the specifics of the coding process.

Think of it like telling a story. Once you know the beginning and how to tell it, you can just keep adding smaller pieces of the story together (recursion) without having to rethink the entire plot each time. You know the main concept (the story), and you just layer more detail (smaller inputs) onto it.

What such inductive definitions exploit is what is sometimes called the optimal substructure property. So, what is complicated base means basically is what you expect from an inductive definition that is you solve the original problem by combining the solution to sub problems.

The optimal substructure property refers to the idea that a solution to a complex problem can be constructed from optimal solutions to its subproblems. In the case of sorting with insertion sort, by sorting a smaller portion of the list, we can produce an optimal sorted list when the entire original list is combined. It’s this property that allows us to recursively sort smaller parts and combine them effectively.

Consider building a large LEGO structure. You first build smaller sections (subproblems) optimally before connecting them. Each well-built section provides a sturdy foundation for the entire structure, ensuring that the overall outcome is structurally sound and aesthetically pleasing.

--