13.4. Complexity Analysis

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 introductory chunk, we establish the context for merge sort and its advantages. It highlights that selection sort and insertion sort both have a time complexity of O(n^2), which is inefficient for large data sets. This serves as a motivation to explore more efficient algorithms such as merge sort, which is designed to sort arrays more effectively.

Imagine trying to sort a large stack of cards using a simple method of checking each card against every other card. This becomes increasingly tedious and time-consuming as the number of cards grows. Instead, using a more strategic method to handle the cards, like merge sort, can significantly speed up the process.

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 independently sorted halves.

This chunk describes how merge sort begins by breaking the array into two halves. It emphasizes that by sorting the left and right halves independently, we can simplify the sorting process into smaller manageable problems. This approach aligns with the divide-and-conquer technique, fundamental to the merge sort algorithm.

Think of organizing a large library. Instead of trying to arrange all the books at once, you first split them into different categories or genres. Once the categories are organized, you can easily sort the books within each category, making the overall sorting much simpler.

So, let us first look at this combining step. So, we are given two sorted list a and b or two sorted array is a and B, and we want to combine them into a single sorted list. ... Eventually, I build up a new stack of sorted list.

In this chunk, we explore the merging process. After sorting the two halves, they must be combined into a single sorted array. This segment illustrates an intuitive way to merge sorted lists by always selecting the smallest element from the tops of both lists and adding it to the new list, effectively maintaining order.

Imagine you are combining two teams of players who are already ranked by skill. To form a new ranked team, you can look at the top players from both teams and choose the best. By always picking the top player, you ensure that your new team starts off in the best possible order.

So, now, how do we use this to sort. As we said our aim is to break up problems into two equal sub-problems. ... until you reach a trivial sub-problem, which is an array of size of 1.

This chunk explains the recursive nature of merge sort, where each time the algorithm is applied, the problem size is halved until reaching the base case of a single element, which is inherently sorted. It emphasizes the elegance of the algorithm—solving complex problems by breaking them down into smaller and more easily manageable pieces.

Consider a massive jigsaw puzzle. Instead of trying to assemble the whole thing at once, you break it down into smaller sections. Once each section is complete, you can easily piece them together until the entire puzzle is assembled.

Let us look at an example before we proceed. ... So, this is how merge sort works. You break it up in two parts, recursively solved two parts using the same strategy and merge them.

In this segment, an example is presented to visualize the merge sort process. It details the division of an array into smaller parts and shows how sorted sections are merged back together. This reinforces the understanding of the merge sort algorithm's operation through practical application.

Picture preparing a large feast with multiple dishes. Each dish requires its own preparation. You handle one dish at a time, ensuring it is perfectly cooked before moving on to the next. Once all dishes are ready, you bring them together for the final presentation, akin to merging the sorted halves.

So, this is generally a principle that can be applied to many problems. ... The crucial thing, is to identify how to break up the problem into disjoint sub-problems.

This conclusion highlights that the principles used in merge sort—dividing the problem into smaller parts and combining the results—can be applied to many different scenarios, not just sorting. Recognizing how to effectively break down complex problems is key to solving them efficiently.

Life often presents complicated projects. If you take a big project (like planning a wedding) and divide it into smaller tasks (guest list, venue, catering), you can manage each part separately. Once completed, all parts come together for the final event, similar to how merge sort assembles sorted arrays.

--