13.2. Iterative Merge Function

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 shorted list or two sorted arrays A and B into A third sorted list C. Well as we saw if one of the two is empty, then I do know do anything I just have to copy the other one. So if there is a no element left in A, then I can just copy there is to B into C. If B is a empty I can copy A into C; otherwise we compare the first element of A and B and move the smaller then go into C, and we repeat this until everything has been moved.

In this chunk, we establish the aim of the merge function, which is to combine two sorted arrays into one sorted array. The approach starts by checking if either of the two arrays is empty. If one array is empty, the function simply copies the contents of the other array into the resulting array. If both arrays contain elements, the function will compare the first element of each array. The smaller element will be added to the new array, and this process will continue until all elements from both arrays are transferred.

Imagine you have two piles of sorted cards. You want to combine them into a single pile. If one pile is empty, you can simply keep the other pile as it is. If both piles have cards, you pick the top card from each pile, see which one has the lower value, and put that card into your new pile. You repeat this process until both piles are exhausted.

So, here is the simple iterative merge function. So, it takes two arrays as input. Take an array a of size m. So, 0 to n minus 1. Let takes an array B, which may be of different size 0 to n minus 1, and the aim is to construct and new array C. Now we know the size of C, because everything there must come here. So, it will be equal to 0 to m plus n minus 1. So, what we do is, we maintain some position. So, we say that okay let i B the current position I am looking at in this, j B the current position I am looking at B, and k B the current position I am trying to fill in C.

In this chunk, we describe how to set up the merging process with specific indices to track our position in each of the three arrays: A, B, and C. We define the sizes of the arrays and maintain index variables 'i', 'j', and 'k' corresponding to the current position in arrays A, B, and C respectively. This setup is crucial for ensuring that we can move through each array correctly as we merge them.

Think of three boxes filled with sorted toys. One box (Array A) has red toys, another box (Array B) has blue toys, and you have a third empty box (Array C) to fill with the sorted toys. You use markers to remember where you are in each box: 'i' points to the next red toy to consider from box A, 'j' points to the next blue toy from box B, and 'k' points to the next empty spot in box C where you will put the next toy.

Now, we know that there are n plus 1 steps. So we put a loop which says this think must run n plus 1 m plus n times. So, if we have already reached the end, if j has already is the end, or if A i is smaller than B j. So, this is the real merge step. If A i is smaller or equal to B j what we will do is, we will copy is value here, and then we will increment i and will increment j.

In this chunk, we discuss the merging logic that is executed in a loop, where the loop continues until all elements from both arrays are processed. The algorithm checks if there are still elements in both arrays. If array A has a smaller or equal element than array B, that element is added to the new array C, and the index for A is incremented. This comparison ensures that the smallest available element is always added next.

Continuing with the toy analogy, imagine you always take the smallest toy (by size) from either the red or blue box to place into the empty box. Each time you take a toy, you remember to move your pointer to the next toy in the box you took from, ensuring that you never miss a toy.

But this also happens in case j is equal to n. If j is equal to n what it means is that, this pointer actually reached all way there. So, there is nothing left to scan. So, j is equal to n means actually beyond the right point. So, it is beyond the point. So, we will just copy everything from A to C.

This portion of the chunk describes what happens when we reach the end of one of the arrays, specifically array B. If the index 'j' for array B has reached its end, it means there are no more elements to discard from array B. In this case, the remaining elements in array A are directly copied to array C, maintaining their sorted order.

Returning to our toy example, if you finish taking toys from the blue box but still have some red toys left, you simply move all remaining red toys into the empty box without needing to compare them anymore, since there’s nothing left from the blue box.

So, the symmetric case is, when we have A i bigger then B j. So, if A i is bigger than B j, then what we want to do is, copy this value here. So, we want to move j up and k up. So, we copy C k is equal to B j, copy the value at B j to C k, and increment both j and k. And like we did earlier, the other reason we might want to do is, as if we have already exceeded the length of.

In this final segment, we further discuss the scenario where the element in array A is greater than the element in array B. In this case, the algorithm takes the element from array B and adds it to array C. Again, both j and k are incremented to process the next elements. Additionally, if array A is fully processed and elements from array B remain, they are copied into array C directly.

If you finish taking the last red toy and realize you still have blue toys left in the blue box, you would place those blue toys into the empty box without any type of comparison, since they are already sorted.

--