14.1. Merge Sort: Analysis

So, we have seen how to use a divide and conquer strategy, we implemented sorting algorithm called merge sort. So, now we want to analyze whether the merge sort actually behaves, better than an order n square intuitive sorts like insertion sort and selection sort.

In this chunk, we introduce the merge sort algorithm and its analysis. Merge sort uses the divide and conquer strategy to sort elements. The analysis aims to compare merge sort's efficiency against simpler sorting algorithms like insertion sort and selection sort, which have a time complexity of O(n²).

Consider organizing a large library. If you sort books one by one (like insertion sort), it takes a long time. But if you split the library into sections and organize them separately before combining (like merge sort), it's faster and more efficient.

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 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 crucial to merge sort. It combines two sorted lists into a single sorted list. During merging, elements from both lists are compared, and the smaller element is added to the final list. This process continues until all elements from both lists are merged into list C.

Think of two people sorting their collection of fruits. One has apples and oranges, and the other has bananas and pears. They can compare their fruits one by one, picking the smallest fruit to form a new, sorted fruit basket together.

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.

In the merging process, each iteration adds one element to the merged list C until all elements from both lists A and B are placed in C. Since A contains m elements and B contains n elements, the merging will take m+n steps, where each step involves only a few constant time operations (comparisons and assignments). Therefore, the time complexity of the merge operation is O(m+n).

Imagine you are filling a large bowl with fruit from two smaller bowls. Each time you pour a piece of fruit from either bowl into the large bowl, it’s like one step in the merge operation, and eventually, the larger bowl fills up with all the fruit.

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. 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.

The overall process of merge sort involves recursively dividing the list into two halves until we reach single elements, then merging these sorted halves back together. The recurrence relation for merge sort can be expressed as T(n) = 2T(n/2) + O(n), which means it takes T(n/2) time to sort each half and O(n) time to merge them. Solving this recurrence gives us the time complexity of O(n log n).

Imagine your list is a stack of cards you need to sort. You keep splitting the stack into two until you have single cards. Then you start sorting these pairs of cards back together (merging) into a neat stack, which is much faster than trying to sort the whole stack at once.

So, we have achieved a significant improvement, because remember that, so far both insertion sort and selection sort your O(n square) and we have come down from O(n square) to O(n log n) by using this divide and conquer strategy.

The efficiency of merge sort, with a time complexity of O(n log n), means it's significantly faster for larger datasets than algorithms like insertion sort or selection sort, which operate at O(n²). This improvement allows for processing larger volumes of data in a reasonable amount of time.

If you have to sort a box of 10,000 books, using the old method (insertion sort) could take forever, whereas with merge sort, you could sort that same box in a fraction of the time, making it manageable and effective.

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.

Although merge sort is efficient, it has limitations. One significant drawback is the need for additional space to hold the temporary merged list. This extra memory requirement can be a disadvantage when sorting very large datasets, as it can lead to memory inefficiency.

Imagine trying to organize a garage sale. If you have limited tables (space) to sort and display items, sorting all your items at once can be unmanageable. You would need to find external tables or boxes to store grouped items until they’re sorted, similar to the extra space needed in merge sort.

--