13.1.1. Introduction to Merge Sort

So, we have seen two intuitive sorting algorithms; selection sort, and insertion sort, but unfortunately for us, both of then 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, the speaker addresses the inefficiency of two common sorting algorithms: selection sort and insertion sort. Both algorithms operate with a time complexity of O(n²), which means that their time required to sort grows quadratically with the number of elements in the array. This becomes prohibitive for large datasets, leading to the search for more efficient algorithms.

Think of sorting a large pile of books. If you manually check and position each book one at a time, it would take a long time if there are hundreds of books. This is similar to how selection sort and insertion sort work. Now, imagine if you could split the pile and organize small sections separately before merging them back together. This would save a lot of time, just like 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 to left and right into independently sorted halves.

Here, the speaker introduces the core concept of merge sort: dividing the problem into smaller subproblems. By splitting the array in half, we can manage the sorting of each half independently. If both halves can be sorted, it implies that the entire array can be sorted by merging the two sorted halves together later.

Imagine you’re preparing a large meal. Instead of cooking everything at once, you decide to prepare the vegetables and the meat separately. Once both dishes are ready, you combine them for serving. This method is efficient and manageable, similar to how merge sort divides the array.

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.

Once we have two sorted halves, the next step is to merge them into one fully sorted array. This combining process is critical for the efficiency of the merge sort algorithm. It involves comparing the smallest elements of each half and placing the smaller element into a new array, continuing this process until all elements are merged.

Imagine you have two friends, each with a sorted playlist of your favorite songs. To create a combined playlist, you listen to the top song from each list, choose the one you want to add to your new playlist, and then move to the next song in the list of the song you just added. After a while, you end up with a perfectly sorted playlist. This mirrors the merging process in merge sort.

So, our aim is to break up problem into two equal sub problems. Solve the sub problems, and there merge the two solution into a final solution. Now I have said that we will break up the thing in two sub problems. So, how do I solve this? Well I will recursively do same thing...

The speaker explains that merge sort uses a recursive approach to sort the array. This means that the sorting function calls itself to sort the left half and the right half. The process of dividing continues until we reach a base case, where an array of size one is already sorted. After sorting the smaller arrays, we merge them to produce larger sorted arrays until the entire array is sorted.

Think about folding a large piece of paper into smaller sections. Each time you fold, you manage a smaller section until you get down to a tiny piece that you can easily arrange. Each ‘fold’ represents a recursive call in the merge sort algorithm.

Let us look at a very simple example. So, supposing you want to merge the two sorted list. So, this is sorted in ascending order and so is this sorted in ascending order. The first step, is to look at the top most...

In this chunk, an example is provided for clarity on how to merge two sorted lists. By comparing the topmost elements of each list, the algorithm selects the smaller element to add to the new sorted list, and this process continues until all elements are transferred. The method illustrates the straightforward nature of the merge process.

Imagine two friends are packing their suitcases for a trip. Each has a list of items they’ve already organized in order of importance. As they pack into a single suitcase, they take turns picking from the most important item in each list, ensuring the suitcase remains organized. This is very like how merge sort combines two sorted arrays.

--