13.1.5. Formalizing Merge Sort Algorithm

So, we have seen two intuitive sorting algorithms; selection sort, and insertion sort, but unfortunately for us, both of them turn out to be order n square. And we know that order n square is not really good enough for sorting large arrays. So, what can we do instead?

So, here is one way to sort an array more effectively. So, suppose we divide the array into two equal parts. So, we just bracket in the middle, we look at the left separately and the right separately. Now assume that we can sort the left and right into independently sorted halves. So, we have the left half sorted, the right half sorted. Now if there is a way to combine the two halves efficiently to get a fully sorted array, then we can say that we have achieved the sorting by breaking it up into two smaller sub problems and combining the result.

In this chunk, we learn that traditional sorting methods like selection sort and insertion sort have a time complexity of O(n²), making them inefficient for large arrays. The solution introduced is the Merge Sort algorithm. The key idea is to break a large array into two smaller halves and sort each half independently. Once sorted, these halves can then be merged back together to form a complete, sorted array. This divide-and-conquer strategy is at the heart of the Merge Sort algorithm, allowing for efficient sorting.

Imagine you have a large pile of papers that are randomly arranged. Instead of sorting them all at once, you decide to split them into two smaller piles. You sort each pile separately and then combine the sorted results. This method is like sorting a long queue at a store by breaking it into two shorter lines and processing each independently.

So, let us first look at this combining step. So, we are given two sorted lists a and b or two sorted arrays A and B, and we want to combine them into a single sorted list. ... So, eventually I build up a new stack of sorted list.

This chunk explains how we can merge two already sorted lists into one sorted list. The process involves comparing the first elements of both lists and moving the smaller element to a new list, continuing until all elements from both lists are transferred to the new sorted list. This melding process allows for the efficient formation of a new sorted array through simple comparisons.

Think of two people organizing their decks of playing cards. Each person has their cards in order from smallest to largest. They start by comparing the top card of each deck, moving the lesser card to a new pile, and repeating the process until all cards are sorted. By doing this, they efficiently create a single organized deck from two organized ones.

So, now how do we use this to sort. As we said our aim is to break up problem into two equal sub problems. ... So, I keep breaking up to the thing into sub problem, until you reach a trivial sub problem, which is an array of size of 1.

Here, we dive into how Merge Sort recursively divides the array into subarrays until we reach the base case, which is an array with only one element. This is crucial because a single-element array is inherently sorted. Once we reach these smaller subarrays, we can then begin to merge them back together in a sorted order, using the merging process previously discussed.

Consider a scenario where a person is tasked with organizing a massive library. Instead of sorting all books at once, they decide to divide the library into sections. Each section is then further divided into smaller shelves until they can handle individual shelves easily. Once organized, they can combine these sorted shelves back into their appropriate sections.

So, let us look at an example before we proceed. So, here is an example of an array that we would like to sort. ... So, this is how merge sort works. You break it up in two parts, recursively solved two parts using the same strategy and merge them.

In this chunk, the lecture walks through an example of sorting an array using Merge Sort. It describes the steps: dividing the array into two halves, recursively sorting those halves, and then merging them back together. This concrete example illustrates how to apply the logical principles previously described, making it easier to understand the practical implementation of the algorithm.

Picture a workshop where a team is assembling complex devices. Instead of building the device as a whole, they break it down into smaller parts, assemble each part separately, and finally combine all the assembled pieces to form the complete device. This illustrates how Merge Sort breaks down and builds up efficiently.

So, let us come back to our merge sort and try to formalize the algorithms in terms of actual code. So, how do I combine two sorted list or two sorted arrays A and B into a third sorted list C. ... So, this is the simple while loop right.

In this chunk, the lecture begins to formalize the merging process through pseudocode. It outlines the steps of comparing elements from two sorted arrays A and B and populating a new array C with these elements in sorted order. This merging function is key to the operation of the Merge Sort algorithm, as it allows the algorithm to efficiently combine sorted arrays.

Imagine a chef combining ingredients from two separate containers to make a new dish. They will systematically compare each ingredient's quality (like freshness) and incorporate them into a single bowl in a way that ensures the result is well-blended and harmonious - similar to how the merging process ensures a fully sorted array.

So, having got merged out of the way. Now, we can look at merge sorted itself. So, if we want to sort a of size n indices C 0 to n minus 1. ... This works in all cases. To analysis this, is not so straight forward, so we will postpone that to the next module.

In this final chunk, we focus on defining the entire Merge Sort algorithm as a recursive function. It includes checking the base condition, dividing the array into halves, sorting each with the same merge sort function, and then merging the sorted halves. This encapsulates the entire procedure in a structured way, showing how recursion and merging work in unison.

Think of an assembly line in a factory where each worker only assembles a part, and once every part is ready, they are sent to the main assembly area to build the final product. Similar to how Merge Sort works, where each function deals with its segment of the array until all pieces are combined into the final sorted array.

--