14.1.1. Introduction to Merge Sort

So, in order to analyze merge sort, we first need to look at the merge operation itself. So, remember that when we merge two sorted list, what we do is, we take both list side by side and we keep copying the smaller of the two elements at the header each list into the final list C.

The merge operation is a critical component of the merge sort algorithm. It involves merging two sorted lists (let's call them list A and list B) into a new list (list C). The process is straightforward: we compare the first elements of both lists (the 'heads') and take the smaller one to be added to list C. This process is repeated until all elements from both lists are merged into list C, maintaining the order.

Imagine you are organizing two stacks of books, one labeled 'Fiction' and the other labeled 'Non-Fiction.' If you want to create a third stack that contains all the books sorted together, you would take the book on the top of each stack and choose the one that is alphabetically first to add to your new stack. You continue this process until all books from both stacks are correctly placed in the new stack.

In each iteration notice that we add one element to C, but the size of C is exactly m plus n, because there are m elements in A and there are n elements in B.

The merging process adds exactly one element to list C in each iteration. Since there are 'm' elements in list A and 'n' elements in list B, the total number of elements that need to be added to list C is m + n. This implies that the number of iterations needed to completely merge the two lists will also be m + n. Therefore, the time complexity for the merge operation is linear, meaning it operates in O(m + n) time.

Think of merging two teams of players from different sports. Team A has 5 players and Team B has 3 players. When forming a unified team, you will have to introduce each player one at a time into the new team until all players from both teams are listed. The total number of introductions needed will be the sum of both teams' players, which in this case is 8.

So, now coming to merge sort itself, what we want to do is, we want to take a list of size n and you want to split it into two lists of size n by 2.

Merge sort uses a divide and conquer strategy. Initially, a list of size 'n' will be split into two halves; each half will roughly be of size n/2. Each of these halves will then be sorted recursively using the same merge sort technique until we ultimately reach lists that are small enough to be trivially sorted (typically lists of size 1). After sorting the smaller lists, the merge operation is applied to combine the sorted halves back together into a single sorted list.

Consider a library that needs to organize books. Instead of organizing all the books at once, they can first split the books by genre into two smaller groups. Each group is then sorted by title. Once both smaller groups of books are in order, they are merged back together to create one fully sorted library, making the organizing process much simpler.

If we have a solution I mean an expression like this two recurrence like this, then how to be solve them.

The time complexity of merge sort can be expressed as a recursive relation: T(n) = 2T(n/2) + O(n). This indicates that merge sort splits the list into two halves (each taking T(n/2) time) and then merges them (which takes O(n) time). By solving this recurrence relation, we find that merge sort operates in O(n log n) time overall, which is significantly faster than the O(n²) time of simpler sorting algorithms like insertion sort.

Imagine you are organizing an event with 100 guests. First, you split them into two groups of 50. Each group is organized separately (which represents the divide part), and then you combine both groups into a single guest list (which represents the conquer part). The time taken to organize each group and then merge them gives you a clearer understanding of how quickly you can organize a large number of guests using this strategy.

The main reason we need extra space and merge sort, because of the merge operation as we saw in order to combine A and B into a list C in linear time you need extra space.

While merge sort is efficient in terms of time, it does have drawbacks, such as requiring additional memory space for the temporary list during the merging process. This could be a disadvantage compared to in-place sorting algorithms which use little to no additional space. However, the efficiency in sorting large datasets often outweighs this issue, especially for large data sets.

Consider a chef in a restaurant who is preparing two large tables of ingredients separately. While preparing each table, he has to set aside additional bowls to mix the ingredients before serving. Even though this additional space may seem wasteful, the chef efficiently organizes everything in the correct order, which makes service quicker. Similarly, in merge sort, the extra space aids in organizing the data efficiently.

--