13.2.1. Description of Iterative Merge Process

So, let us first look at this combining step. So, we are given two sorted list a and b or two sorted arrays a and B, and we want to combine them into a single sorted list. So, this is something that we can easily do. Supposing we have two stacks of cards in front of us. Each of them is arranged in the same way in ascending order. Then what we will do is we look at the top most cards in each stack, and take the smaller of the two, and move it to a new stack.

In the merging process, we have two sorted lists (or arrays). The goal is to combine them into a single sorted list. We can visualize this by thinking of it as two stacks of cards organized in ascending order. To merge these stacks, we compare the top cards of both stacks. We take the smaller card and place it onto a new stack. We repeat this process until we have transferred all the cards into the new stack in sorted order.

Imagine you have two friends who each have a set of playing cards arranged by number. To create a combined sorted deck, you would ask each friend to show you their top card, compare them, and place the lower card into a new pile. You'd keep comparing the next top cards from each pile and repeat this until you've merged all cards into one sorted pile.

Let us look at this in a very simple example. So, supposing you want to merge the two sorted list. So, this is sorted in ascending order and so is this sorted in ascending order. 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.

In our example, we have two sorted lists. To merge them, we first look at the topmost elements of both lists. We compare these elements and place the smaller one into our new sorted list. This process continues: each time comparing the topmost elements from both lists and transferring the smaller one to our new list. Eventually, when one stack is empty, we simply append the remaining elements of the non-empty stack to the new list.

Imagine you are stacking books of different sizes. You pick the shorter book from the two piles in front of you and add it to a new pile. Once one pile is gone, you simply transfer all remaining books from the other pile without any need to compare them again since they are already sorted.

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 an array from a0 to an by separating it at the midpoint and sorting each half before merging.

To perform the merge sort, we start by dividing the array into two halves. Each half is then sorted by recursively applying the same sorting strategy. When the base case is reached (when the sub-array size is one), the array is implicitly sorted. The next step involves merging these sorted halves back together into a single sorted array. By breaking the problem down into smaller parts, we can simplify the sorting task.

Consider organizing a big event where you have to sort guest names. Instead of trying to sort all names at once, you could break them into two smaller groups - each group sorted separately. Once both groups are sorted, you merge the lists by comparing names, just like combining two sorted arrays.

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?

We formalize the merging process into a function that takes in two sorted arrays A and B, and merges them into a new array C. The function runs through the elements of A and B, comparing them to construct the sorted array. We maintain index pointers for each array and carefully copy elements to ensure the new list remains sorted.

Think of a librarian tasked with cataloging books from two different shelves into a single alphabetical order. They will get one book from each shelf, compare their titles, and place them in a new shelf sequentially. They do this until they’ve gone through all the titles, ensuring that the final shelf appears in perfect order.

--