13.3.2. Base Case for Recursive Merge Sort

So, here is one way to sort an array more effectively. So, suppose we divide the array into two equal parts. So, we just bracket in the middle, we look at the left separately and the right separately. Now assume that we can sort the left and right into independently sorted halves. So, we have the left half sorted, the right half sorted. Now if there is a way to combine the two halves efficiently to get a fully sorted array, then we can say that we have achieved the sorting by breaking it up into two smaller sub problems and combining the result.

The base case in a recursive algorithm is critical for stopping the recursion. In merge sort, when we recursively divide the array, we eventually reach the point where we have an array size of one. An array with a single element is already considered sorted because there is nothing to compare it to. This is where our recursion can stop, allowing us to start combining the results of our sorted halves.

Think of organizing a deck of cards. If you only have one card, you don't need to do anything because it's already in order. But when you have more cards, you can break them down into smaller groups, sort those, and then combine them back together.

Now we will apply merge sort separately to these parts; finally, we will merge the answer. So, having applied merge sort to the left part, we must again break it up into two parts. I would take this point in dividing into two parts. And similarly on the right, I will have to take this point, and divide into two parts. Now we could say that we can easily do array of size two, but let us just keep going till we reach the base case.

To sort an array effectively, merge sort works by continuously dividing the array into halves until you reach the base case, where the array becomes so small (one element) that it is trivially sorted. Each half is then processed independently so that once they are sorted, they can be merged together.

Imagine a large stack of books that you want to organize alphabetically. You could first split the stack in half, and then keep splitting each half until you have individual books. Once each book is a separate entity, you can then start placing them in order from smallest to largest and progressively merge them back into a single sorted stack.

Now I want to merge these two arrays into a sorted segment of length 4. So, again apply merging. So, note that 22 will come first then 32 will come here, then 43 will come here, and then 78 will come here.

Once the two sorted halves are ready, the next step is the merging process where we take two sorted segments and combine them into one sorted segment. This is done by comparing the elements from the two segments and choosing the smaller element to go into the final array, repeating until all elements are merged into one sorted segment.

Think of friends at two tables getting together to form a single large table. Each table has its own arrangement (sorting), but when they combine, they need to ensure that they keep the same arrangement while sitting next to each other. They compare who has the smallest number, so they can determine who sits down first.

--