14.1.2. The Merge Operation

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

The merge operation is a crucial part of the merge sort algorithm. It takes two sorted lists (let's call them A and B) and combines them into a new list (C) that is also sorted. The process involves comparing the first element of each list, copying the smaller one into the result list C, and then moving the pointer forward in that list. This is repeated until all elements from both lists are copied into C.

Imagine you are sorting two stacks of playing cards. You have one stack with cards numbered 1, 3, and 5, and another stack with cards numbered 2, 4, and 6. To merge them, you look at the top card of each stack, pick the smaller card, and place it on a new table until both stacks are empty. At every step, you ensure the new stack is always sorted.

So we have a list A, which runs from 0 to m minus 1 and we have another list B, which runs from 0 to n minus 1 and we produce the output in a third list C which has indices from 0 to m plus n minus 1.

When performing a merge operation, we set up indices for both lists A and B and also for the output list C. We initiate comparisons between the elements pointed at by the indices of A and B. Depending on which element is smaller, we copy that element into C and move the corresponding index forward. This continues until we've processed all elements from both A and B.

Think of it like organizing your bookshelf. You have two sections of books sorted by height. You want to combine them into one section while keeping everything in order. You pull the shortest book from either section and place it on the new shelf first, then repeat the process.

So, there are m plus n elements and in each iteration of this loop, one element gets added to C, either in this if or in this if, k is incremented. So, there is a bound of m plus n steps for this loop...

The merge process is efficient because, for every iteration, we are guaranteed to add one element to the merged list C. Since there are a total of m + n elements to merge, we can conclude that the maximum number of operations needed for the merge will be in the order of m + n. Each comparison and copy operation counts as a constant time action, leading to an overall time complexity that is linear with respect to the total number of elements.

If you think about putting together a jigsaw puzzle, every time you find a piece that matches, you place it correctly, which counts as one move. No matter how many pieces you have, the total number of moves to finish the puzzle is proportional to the number of pieces.

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. And then, we sort these separately and then we merge.

Merge sort works by recursively dividing the list into two halves until each sublist contains a single element. The time complexity for sorting the whole list is characterized by a recurrence relation. For a list of size n, it requires sorting two lists of size n/2 and merging them back together, which gives us the formula T(n) = 2T(n/2) + O(n).

Imagine you're organizing a large photo album. You keep dividing the album into smaller sections until each section has just one photo. Then, as you start merging those sections back together, you ensure that each smaller collection is already in order, making the final album come together efficiently.

So, we can say that overall merge sort is O(n log n).

The final time complexity of merge sort combines the logarithmic dividing of the list (the number of times we can split n until we reach a single element) with the linear merging of elements back together. This gives us a time complexity of O(n log n), which is significantly more efficient than quadratic sorts like insertion sort and selection sort.

It's similar to organizing a large group of people into teams. If you take a team of 8 people, it might take longer to sort them by height directly rather than grouping them into smaller sub-teams of 2 or 4 people first, sorting each small group, and then merging them together for a final arrangement.

The main problem with merge sort is that it requires extra space.

Merge sort is not always the most practical sorting algorithm because it needs additional space to hold the merged array (list C), which can be a significant drawback, especially with very large datasets. This is due to the nature of the merging process where the original lists A and B cannot be merged in place without extra space.

Consider a situation where you're trying to clean your room by merging two piles of clothes. If you only have a small box to store everything while sorting, it means you wouldn’t effectively fit everything in without having extra space, making the process cumbersome and inefficient.

--