13.3. Recursive Merge Sort

So, we have seen two intuitive sorting algorithms; selection sort, and insertion sort, but unfortunately for us, both of them turn out to be order n square. And we know that order n square is not really good enough for sorting large arrays. So, what can we do instead?

In this chunk, we learn about the limitations of the selection sort and insertion sort algorithms, which both have a time complexity of O(n²). This means that their efficiency decreases significantly as the size of the input array increases. As a solution to this problem, the speaker introduces merge sort as a more efficient alternative for sorting larger arrays.

Imagine trying to sort a stack of 1000 cards by going through them one by one, comparing each pair (like selection sort and insertion sort). This approach becomes impractical with a high number of cards due to the excessive time it would require. Merge sort, on the other hand, would be like splitting the stack into two piles, sorting each pile, and then combining them, which is much faster.

So, here is one way to sort an array more effectively... 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...

This chunk explains the core concept of merge sort: dividing the array into two halves. After dividing, the algorithm recursively sorts the left and right halves separately. The importance of recursion in this method lies in its ability to manage smaller problems, which are easier to solve than a larger one.

Consider a large library where you need to organize books. Instead of organizing all the books at once, you could divide them by genre into smaller groups, organize each group separately, and then combine the organized groups back into the library.

So, let us first look at this combining step. So, we are given two sorted lists A and B, and we want to combine them into a single sorted list...

This chunk details how to merge two sorted arrays into a single sorted array. It describes a practical method of comparing the top elements of both arrays and selecting the smaller one to add to a new merged array. This process continues until all elements from both arrays have been added to the new array, ensuring that the final merged array remains sorted.

Think of merging two sorted lists of event invitations. If one list has names ordered alphabetically from 'Alice' to 'Bruce' and another goes from 'Anna' to 'John', you would check the next name from both lists and put the smaller name first on the final list until all names are organized.

So, we will sort A0 to A(n/2) and A(n/2) to A(n-1) to make it distinct. The strategy is to recursively break down the array until we reach the base case, an array of size 1...

This chunk reveals how the recursive nature of merge sort allows breaking down the original problem into smaller problems until reaching subarrays that are trivially sorted (arrays of size 1). It emphasizes how merge sort re-applies the sorting and merging processes repeatedly until the entire array is organized.

Visualize sorting a very large box of toys. Rather than tackling the entire box at once, you could take a few toys, organize them, and then sort smaller sets until you eventually work through the entire pile.

Now I want to merge these two arrays into a sorted segment of length 4... So, merging these two sub-arrays of size four will give me the final answer.

In this chunk, the process of merging sorted segments of the array is again illustrated using an example where subarrays are merged step by step. The detailed explanation of how to choose the smallest elements continues to highlight the importance of maintaining order through the merging process, which ultimately leads to the fully sorted array.

Picture this as assembling a jigsaw puzzle: you first find the corner pieces (small sorted sections), then connect those pieces together (merging) to create a larger, completed image, repeating until the whole puzzle is complete.

--