Binary merge

The binary merge operation is a very common operation in computer science, where two individual sorted sequences are merged into one larger sorted sequence. Merging is the backbone of many different sorting tasks, making this operation useful in a broad array of applications.

Considering this information answer parts a and b below.

a)

Write the function:

std::queue binary_merge(std::queue one, std::queue two)

which performs an iterative binary merge.

Here are the specifications:

• The elements of the queues one and two are expected to be in increasing order from front to back. The returned result is a queue containing the combined elements from one and two in increasing order from front to back.
• The queues one and two are passed by value, so binary_merge receives copies of the input queues and can freely modify them. There is no requirement on the ending state of those queue copies.
• binary_merge takes in two queues and returns a queue. You are not to use any additional data structures (e.g. no vectors, no arrays, and so on)
• The two queues are not required to be the same length. One could be enormous; the other could be a single element. It is also possible that one or both of the input queues is empty. Be sure your function handles all possibilities – write as many test cases you need to confirm!
• There is no special-case handling of duplicate values. Merging {1, 2, 2} with {1, 3} results in {1, 1, 2, 2, 3}.

Important! You must implement binary_merge using iteration, not recursion.

b)

Implementing recursive_multi_merge

Write the function

std::queue recursive_multi_merge(std::vector> const& all);

that applies the power of recursive divide-and-conquer to implement a much more efficient variant of a multi-way merge.

The recursive strategy for recursive_multi_merge follows these steps:

Divide the vector of k sequences (queues) into two halves. The “left” half is the first k/2 sequences (queues) in the vector, and the “right” half is the rest of the sequences (queues).

Feel free to use the following function to extract a contiguous part of a std::vector (this function is also part of the starter code):

Make a recursive call to recursive_multi_merge on the “left” half of the sequences to generate one combined, sorted sequence. Then, do the same for the “right” half of the sequences to generate a second combined, sorted sequence.

Use your binary_merge function to join the two combined sequences into the final result sequence, which is then returned.

Important! You must implement recursive_multi_merge using recursion, not iteration.

Notes

• Your binary_merge function should operate iteratively (not recursively). Your recursive_multi_merge should operate recursively (not iteratively).
• Your recursive_multi_merge should call your binary_merge function.

 

Transcribed Image Text:

// extract a contiguous range of elements from a given vector template std::vector extract_elements ( { std::vector const& v, std::size_t first, std::size_t length) std::vector result; if (first // extract a contiguous range of elements from a given vector template std::vector extract_elements ( { std::vector const& v, std::size_t first, std::size_t length) std::vector result; if (first