13.1. 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?

This chunk introduces the limitations of basic sorting algorithms like selection sort and insertion sort, which have a time complexity of O(n²). This means they take much longer to sort large arrays compared to more efficient algorithms. It sets the stage for discussing merge sort as a more effective sorting solution.

Imagine trying to sort a deck of cards by comparing every card with every other card. This is laborious and time-consuming, especially as the number of cards increases. Now, consider a method where you divide the cards into two piles, sort each pile, and then combine them. This method is much more efficient.

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.

This chunk explains the initial step of the merge sort algorithm: dividing the array into two equal halves. By doing this, we can tackle the sorting problem in manageable pieces. The idea is that if we can sort each half separately, we can then combine them into a fully sorted array.

Think of dividing a large pizza into two halves. You can first cut both halves into smaller slices and ensure each slice is evenly cut, making it easier to handle. Once both halves are evenly cut, you can combine them back into a whole pizza without any leftover uneven pieces.

So, let us first look at this combining step. We are given two sorted lists A and B, and we want to combine them into a single sorted list. This is something that we can easily do... eventually we build up a new stack of sorted list.

This chunk discusses the merging step of the merge sort algorithm. When we have two sorted arrays (or lists), we can efficiently combine them by comparing the smallest elements of both and adding them to a new list in sorted order. This continues until all elements from both arrays are merged.

Imagine two friends pouring their favorite candies into one big bowl. They each sort their candies by colors first. Then, as they take turns adding their candies to the bowl, they always add the candy with the lowest number first, ensuring a beautifully arranged bowl without any mixed colors.

So, let us look at this in a very simple example. So, supposing you want to merge the two sorted lists. So, this is sorted in ascending order and so is this sorted in ascending order... The same way here 30 should come here, then 57, then 63, and then 91.

This chunk provides a concrete example of how merging works with two sorted arrays. It illustrates the step-by-step process of comparing elements from both arrays and inserting them into a new sorted array until all elements are merged correctly.

Picture two teams running a relay race. Each runner only hands the baton to a teammate who is ready at the finish line—only players who are at the front get to participate. As each baton is passed, they ensure that everyone is positioned perfectly to form a complete winning team.

Now how do we use this to sort. As we said our aim is to break up the problem into two equal sub problems. Solve the sub problems and then merge the two solutions into a final solution.

This chunk explains the recursive nature of merge sort. The algorithm continually divides the array into smaller parts until the base case (an array of one element) is reached, which is inherently sorted. It then merges these sorted parts back together.

Think of a large crowd of people wanting to find their seats for a concert. Instead of trying to fit everyone in at once, they group together by smaller sections. Once those sections are organized, they will make their way in an orderly fashion to create a completely filled concert hall.

Notice that for convenience we have taken something where I can keep dividing by 2, but there is no limitation in merge sort; it will work for any size.

This chunk highlights the flexibility of merge sort in handling arrays of any size, not just those that can be divided evenly. The algorithm can still function correctly even when the array size is odd, demonstrating its robustness.

Imagine a sports event where teams are being formed. Even if one team has more players than the other, the game can still continue. Each player participates to the best of their ability, ensuring the game remains fair and enjoyable.

So, let us come back to our merge sort and try to formalize the algorithms in terms of actual code... merge sort into a sub array L. We will sort the right half into sub array R...

This chunk begins the transition from the conceptual understanding of merge sort to its actual implementation in code. It outlines the basic structure and flow of the merge sort function, emphasizing the recursive patterns for sorting both halves and merging them again.

Consider following a recipe to bake a cake. The recipe guides you through each step, from mixing ingredients, baking, to finally frosting. Each step follows logically from the previous, ensuring a delicious cake at the end. Similarly, the code follows a specific structure to ensure that merge sort completes successfully.

--