13.4.1. Analysis of Merge Sort Complexity

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?

The introduction highlights the limitations of traditional sorting algorithms like selection sort and insertion sort, which have a time complexity of O(n^2). This means they become inefficient when handling large arrays due to the quadratic growth of operations as the number of elements increases. The introduction sets up the need for a more efficient algorithm, leading to the discussion of Merge Sort as a viable alternative.

Imagine trying to sort a large bookshelf randomly filled with books using trial-and-error methods, like picking two books at a time and swapping them until they are sorted. This is inefficient for a massive collection. Instead, using a methodical approach like Merge Sort is akin to dividing the bookshelf into manageable sections, sorting each section, and finally putting them back in order.

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.

Merge Sort works by dividing the original array into two halves. It sorts each half individually and then merges the sorted halves into a single sorted array. The key idea here is to break down a complex problem (sorting an entire array) into simpler sub-problems (sorting smaller arrays), solving each independently, and then combining results to achieve the final goal.

Consider sorting a large group of students based on their heights. Instead of comparing every student with every other student (which is time-consuming), you can split them into two groups, let’s say, boys and girls. Sort each group separately based on height and then combine the two sorted lists by comparing heights from the end of each group alternately.

So, let us first look at this combining step. So, we are given two sorted lists a and b or two sorted arrays a and B, and we want to combine them into a single sorted list. So, this is something that we can easily do.

The merging step involves taking two pre-sorted arrays (let's call them 'a' and 'b') and combining them into one sorted array. This is done by comparing the smallest elements of each array and taking the smaller one to add to the new sorted array. This process is repeated until all elements from both arrays are combined into the new array in sorted order.

Think of two piles of sorted cards (one pile is sorted by name and the other by age). To combine them into one pile sorted by both criteria, you pick the smallest or 'next' card from both piles, putting the smaller one on top until both piles are merged into one.

So, 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. So, we will sort a[0] to a[n/2] and a[n/2] to a[n-1] to make it distinct. So, we have a with indices 0 to n-1. So, we take n/2-1 and n/2 as the midpoint. So, we sort this separately, and then we merge them.

The recursive nature of Merge Sort emphasizes that to sort an array, we continually split the array into halves until we reach the base case, where an array can no longer be divided (an array with a single element is inherently sorted). After reaching the base case, we start merging the sorted arrays back together, thus building up the full sorted array from smaller sorted arrays.

If you were to build a large jigsaw puzzle, rather than trying to assemble the entire puzzle at once, you could sort out the corner pieces, border pieces, and interior pieces into smaller sections. Once these smaller sections are completed, you can effectively combine them to reveal the completed puzzle.

So this is generally a principle that can be applied to many problems. So, if you can take a problem, and divide it into two or more parts; such that this part can be solved independently of that part, and there is no overlap. You solve this separately, you solve this separately, and now you want to somehow combine. In this particular algorithms combination is merging.

The core principle of Merge Sort emphasizes that many complex problems can be simplified by breaking them into smaller, independent problems that are solved separately, and then combined. The merging process in Merge Sort acts as a model for efficiently bringing together these solutions. This principle is foundational in designing algorithms beyond just sorting.

Imagine planning a big event, like a wedding. Instead of handling every detail all at once, you can break tasks into manageable parts: venue selection, catering, invitations, etc. Each part is managed independently before combining all into a successfully coordinated event.

--