14.1.4. Improvement Over Other Sorting Algorithms

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 paragraph, the focus is on comparing merge sort with the traditional sorting algorithms like insertion sort and selection sort, which both have a time complexity of O(n²). By implementing the merge sort using a divide and conquer strategy, we can analyze its efficiency relative to these less efficient algorithms. The emphasis is on understanding if merge sort brings about significant improvements in performance.

Imagine sorting a stack of cards using two approaches. The first approach, like insertion sort, has you pick each card one at a time and find the right position for it in the newly sorted stack, which can take a long time with lots of cards. The second approach, like merge sort, allows you to split the cards into smaller stacks, sort those smaller stacks quickly, and then combine them—making the overall process faster.

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 crucial to the merge sort algorithm. It involves taking two already sorted lists and merging them into a single sorted list. During this process, we compare the smallest elements from each list and insert the smaller one into our new list. We repeat this until both lists are fully merged. This operation effectively combines the sorted lists while maintaining order.

Think of merging two sorted grocery lists. You have one list with apples, bananas, and grapes, and another list with apricots and oranges. By looking at the first items of both lists and combining them into a single ordered list—first taking the apricot, then apple, and continuing this way—you can create a final list that is also in order.

So, we have over all order m plus n steps, but m plus n is of course, bounded by 2 times the maximum of m plus n. So, we can just say that this thing takes order of maximum m plus n.

The time taken for the merging process can be measured as O(m+n), where m and n are the sizes of the two lists being merged. Since each list contributes one element at a time to the new sorted list, the number of steps is equal to the total number of elements. This linear time complexity is significant compared to other sorting methods that require quadratic time.

Imagine a race where two runners start from different points and run towards the same finish line. If one runs twice the distance of the other, you can think of merging their journeys at the finish to see who got there first. Regardless of where they started, the total time to finish is determined by the distance both ran together.

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.

Merge sort works by recursively breaking down a larger list into smaller halves until those halves contain a single element. This is designed to take advantage of the sorting already done in these smaller parts. The formula t(n) = 2 * t(n/2) + n illustrates this breakdown: sorting two halves of the list and merging them requires linear time.

Consider an organizing project where you have to sort a collection of books. Instead of sorting all your books at once—which can be overwhelming—you divide them into smaller categories, like fiction and non-fiction, sort those, and finally combine them into a single organized shelf. This way, sorting becomes manageable.

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.

By utilizing the divide and conquer strategy in merge sort, we have reduced the time complexity from O(n²) to O(n log n). This is a substantial improvement because sorting large sets of data becomes much more feasible with this reduced time complexity. The n log n complexity allows for handling larger datasets efficiently compared to O(n²) which becomes impractical as data size increases.

Think of organizing a large library. If you were to sort the books without a plan, you’d be spending a lot more time moving books around (O(n²)). But, if you first separate them by sections (fiction, non-fiction), and then sort each section, you’re much faster (O(n log n)).

If we assume as we have said that a reasonably standard desktop machine can do 10 to the 8 operations per second, then the size of the feasible input of what we can sort with a sorting algorithm, of course from 10,000 for an n square algorithm to 10 million or 1 crore for an n log n algorithm.

This explanation gives a practical view of the efficiency of merge sort compared to other algorithms. It states that on a typical computer capable of 100 million operations per second, the feasible input size for O(n²) algorithms is about 10,000 elements, while O(n log n) can handle up to 10 million. This scalability highlights the practical advantage of using more efficient algorithms for larger datasets.

Imagine you’re trying to sort ratings for a book—by hand, it's incredibly slow when you have only a few reviews (like O(n²)). But with a good sorting process like merge sort, you can organize ratings smoothly from thousands of readers in no time, making it easier to analyze popularity.

--