Suppose you have two sorted arrays and you would like to merge them together into one sorted array.

A motivating example

Now, suppose you had two piles of examinations, each of which is sorted, and you would like to create a single sorted pile. You'd look at both piles, and you see Abbasi and Agrawal,

so from the left pile, you choose Abbasi's examination and turn it face-down in front of you.

The next name in the left pile is Abramowicz, so again, you turn that examination face-down on top of Abbasi's examination.

The next name on the left pile is Andersen, so now you take Agrewal's examination from the right pile and place it face down on top of Abramowicz's examination.

You continue with this until the last examination in the right pile is Yeong, while the pile on the left has Youssef,

so you take Yeong's examination and place that examination face down on the pile in front of you.

Now, you still have four examinations on the left pile, but it doesn't matter anymore, you just place the remaining pile face down on the already-sorted pile of examinations.

You now turn that pile over, and you have a stack of sorted examinations.

We will now formalize this process.

Formal description

Now, let's formalize this algorithm, but now for two arrays: suppose we have two sorted arrays, array0 and array1 with capacity0 and capacity1 entries, respectively.

Try to come up with a description of your algorithm for merging two arrays:

• What variables will you require and how are they initialized?
• How will you loop through the two arrays to ensure that both arrays are merged into one? Are you going to use while loops or for loops?

You should try to work this out on your own; however, if you cannot, you are welcome to look at the following hint.

Function declarations

We will start by authoring the simplest function, and then progress to making this function more useful.

First, start by writing a function that takes two arrays and returns a new dynamically allocated array that is the merged array. Because the caller knows the capacity of both arrays, the caller must know the capacity of the merged array, so all you need return is the address of the first entry of the new array:

int *merge( int array0[], size_t capacity0,
            int array1[], size_t capacity1 );

Next, suppose the caller actually had an array ready in which to merge the two arrays; in this case, it would be a waste of time to allocate memory for a new array. Thus, instead, we could have another implementation that allows the user to pass the array into which the two given arrays are being merged into

void merge( int array0[], size_t capacity0,
            int array1[], size_t capacity1,
            int merged_array[] );

Next, suppose the user is passing you an array, but may want you to start inserting the new entries at a position other than the first entry of the passed array. Of course, it is the caller's responsibility to ensure that the array is sufficiently large, but in this case, let us also include an additional parameter that allows the user to pass the initial index:

void merge( int array0[],       size_t capacity0,
            int array1[],       size_t capacity1,
            int merged_array[], size_t k_initial );

This will assign the entries of merged_array[] from k_initial to k_initial + capacity0 + capacity - 1.

The default value of k_initial should be 0.

Further changes to these algorithms

We can optionally make two further changes to our algorithm:

1. we can use templates, and
2. we can use our Array class.

Templates

The only significant change you can make to improve this algorithm is to have it use templates; after all, it does not matter whether or not you are attempting to merge an array of int or an array of double or an array of unsigned long.

template <typename T>
void merge( T array0[],       size_t capacity0,
            T array1[],       size_t capacity1,
            T merged_array[], size_t k_initial );

Using our Array class

We should now also be able to use our array class that we have previously developed.

template <typename T>
void Array<T>::merge( Array const ∓array0, Array const ∓array1,
                      size_t k_initial = 0 );

You should assume that this is a member function that says: merge the two sorted arrays into this array starting at the position k_initial.

Questions and practice:

1. What happens if you pass your merge(...) function two arrays that are not sorted? What does the result look like?

2. Write test functions to ensure that your algorithm works. Make sure that your algorithm works when capacity0 == 0, when capacity1 == 0 or when both are zero.