13.2.2. Implementation of Merge Sort

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? Here is one way to sort an array more effectively. 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.

Merge Sort begins by identifying that traditional sorting methods are inefficient. It proposes an alternative approach by splitting the array into halves. This division allows the sort operation to treat smaller sections of the array individually, leading to improved efficiency.

Imagine organizing books on a shelf. Rather than tackling the whole shelf at once, you decide to pick a few books, sort those, and place them back. Then you repeat this for the next set of books, ultimately leading to an organized shelf without getting overwhelmed.

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.

Once the two halves of the array are sorted, the next step is to merge them. This involves comparing the elements of both sorted arrays, taking the smaller element, and placing it in a new array. This efficient combination keeps the merged array sorted as well.

Think of two lines of kids, each holding colored balls sorted by size. To combine them into one line, you would compare the balls held by the front kids in each line, take the smaller one, and place it in a new line, thus maintaining order.

Let us look at this in a very simple example. So, supposing you want to merge the two sorted lists. So, this is sorted in ascending order and so is this sorted in ascending order. So, the first step, is to look at the top most. So, let us assume that in terms of top most these are written like this. So, I have this stack, and I have this stack. So, I look at the top most elements, and then I say that the smaller of the two must be the top most element of my new stack.

As an example of merging, we start with two sorted lists. By examining the first element of each list and comparing them, we can choose the smallest to add to a new sorted list. This process continues until all elements have been moved into the sorted list.

Imagine you have two boxes of sorted candies. You compare the first candy from each box, pick the smaller one, and place it in a new box. You keep doing this until all candies are in the new box, perfectly sorted by size.

So, now, how do we use this to sort. As we said our aim is to break up the problem into two equal sub problems. Solve the sub problems, and then merge the two solutions into a final solution. So, we will sort a 0 to a n by 2 a n by 2 n minus 1 to make it distinct. So, we have a with indices 0 to n minus 1. So, we take n by 2 minus 1 and n by 2 as a midpoint.

The Merge Sort algorithm works recursively. It divides the array into smaller arrays until it gets down to arrays of size one. At this point, each array is already sorted. The algorithm then begins to merge these sorted arrays together, working its way back up to the original array size while maintaining the sort order.

Consider building a large puzzle. You break it down into smaller sections, complete those sections first, and then combine them. This way, you ensure that each part is done correctly before tackling the bigger picture.

Now I want to merge these two arrays into a sorted segment of length 4, and these two arrays it was sorted segment of length 4. So, again apply merging. So, note that 22 will come first then 32 will come here, then 43 will come here, and then 78 to come here.

When merging larger sections that have themselves already been sorted, the algorithm continues to compare the front elements of both arrays and transfers them to a new array in sorted order. This process guarantees the final array is correctly sorted as well.

Visualize an artist mixing two halves of a painting. Each half is already well-painted. As they work together, they ensure that the colors blend smoothly without clashing, creating a harmonious final piece.

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 lists or two sorted arrays A and B into a third sorted list C.

The merge sort algorithm can be outlined in pseudo-code and then translated into a programming language. This structured approach allows programmers to easily implement the sorting method, ensuring that the merging of two sorted lists is done with clear logic and efficiency.

Think of writing a recipe for a cake. You outline each step needed to mix ingredients and bake. Having a clear recipe helps others to replicate your process accurately, just like coding allows others to create an algorithm.

--