Lesson 149s: Hint for merging two sorted arrays
Suppose we have two sorted arrays, array0 and array1 with capacity0 and capacity1 entries, respectively.
If we are to merge these two into a single array, that new array must have capacity equal to capacity0 + capacity1. Let us allocate an array of that capacity and call it array_merged.
We will step through each of the two arrays entry by entry, and copy the next largest to the new array. Let us designate these indices as k0, k1 and k_merged, each initialized to 0.
At each step, we will examine array0[k0] and array1[k1] and see which is next, and copy that to array_merged[k_merged]. If the first had the smaller entry, we increment k0, while if the second has the smaller entry, we increment k1. In either case, we increment k_merged.
We keep going until both arrays have at least one more entry to copy over; that is, we keep going as long as k0 < capacity0 and k1 < capacity1.
Once we finish this, there must be at least one more element in the non-empty array—copy the rest of these over to the new array.
Department of Electrical and Computer Engineering
University of Waterloo
200 University Avenue West
Waterloo, Ontario, Canada N2L 3G1
Phone: +1 519 888 4567 extension 37023
Fax: +1 519 746 3077
Website maintained by Douglas Wilhelm Harder