14.1.5. Applications of Merge Operation

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.

So, this was the code that we wrote last time. So, basically 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. So, what we do is, we start by putting an index i, j into these two list and index k into the list C and we compare these two values and we take the smaller of the two values and move it. And then be move this and then we keep moving these two indices and all the while we keep moving k. So, the question is how long does this take?

In the merge operation, two already sorted lists are combined into a single sorted list. The process works by simultaneously comparing the first elements (heads) of both lists and copying the smaller element into a new list C. This operation continues until all elements from both lists are copied into C.

We utilize three indices: i for list A, j for list B, and k for list C. The merging takes at most m + n steps where m is the number of elements in list A and n is the number of elements in list B. Each iteration moves either the index i or j forward by 1, ensuring that the total number of merged elements equals m + n. Since each comparison or assignment involves a constant number of operations, we conclude that the time complexity for the merge operation is O(m + n).

Imagine two queues at a grocery store, with customers waiting to check out. The first queue (list A) has customers with even-numbered items, and the second queue (list B) has customers with odd-numbered items. The cashier (merge operation) takes one customer from each queue (comparing heads) and lets the one with, say, fewer items go through first. By continually doing this until both queues are empty, we effectively combine both groups into one, sorted by the number of items, analogous to how lists are merged while maintaining order.

So, 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 and each of them will eventually make it to C. So, there are m plus n elements and in each iteration of this loop, the loop that we had before, in each iteration of this loop, one element gets added to C, either in this if or in this if, k is incremented.

Each time we perform the merge operation, we are guaranteed to add one element to the newly formed list C. Given that we have m elements from list A and n elements from list B, the size of list C will eventually equal m + n. This means that the merge operation must perform m + n iterations to ensure that all elements from both lists are accounted for. With each iteration consisting of constant time work (comparing elements and adding to list C), the overall complexity remains linear, confirmed as O(m + n).

Think of a waiter who is tasked with collecting all the orders from two tables to deliver to the kitchen. Each order corresponds to an item from lists A and B. For every order taken from either table, the waiter writes it down. Regardless of which order he picks first, at the end of this process, he has written down orders for every item served at both tables, analogous to how every element is processed and added to the result list through the merge operation.

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. And then, we sort these separately and then we merge. So, in order to do this, it is very clear that if we look at t n as a time taken by merge sort on an input of size n, then this requires us to sort two lists of size n by 2 and then, as we have seen it takes order n time in order to merge that.

Merge sort uses a divide-and-conquer approach. Initially, we divide the list of size n into two halves of size n/2. Each half is then sorted recursively using merge sort, which again involves further splitting down until each sub-list consists of a single element. Finally, we utilize the efficient merge operation to combine these sorted sub-lists back into one sorted list. The time complexity for the entire merge sort process is then expressed as T(n) = 2T(n/2) + O(n) due to the sorting of the smaller lists and the merging step, leading to a final complexity of O(n log n).

Imagine organizing a large set of books by first splitting them into smaller manageable sections (like themes or authors). Each small section gets individually arranged (sorted), and once all are organized, you combine them back into a large, coherent library with all topics systematically sorted. This process of iterative refinement is much more efficient than trying to organize all the books at once.

So, merge sort though it is an order n log n sorting algorithm and therefore it is significantly faster than insertion sort or selection sort, it does have some short comes. The main problem with merge sort is that it requires extra space. See, when I take A and B and I merge it into C, it is almost impossible to do this without storing the merge array in a separate place.

While merge sort is efficient, its major downside is the need for additional memory space for the temporary array used during the merge operation. This extra space requirement is a critical consideration, especially when sorting large datasets, because it can significantly increase memory consumption. Furthermore, merge sort is inherently recursive, which may lead to overhead due to function calls, making it less performant for certain situations compared to alternative algorithms that may operate in-place.

Think of packing for a vacation. You have a suitcase (your main data), but every time you need to organize your clothing, you pull out a second suitcase (extra space for sorting). While this helps in organizing (efficiently sorting your data), carrying two suitcases around is cumbersome and consumes more energy (memory) than if you could just manage everything in a single suitcase.

--