A Merge algorithm merges two sorted input arrays into a sorted output array, by repeatedly comparing the smallest elements of the two input arrays, and moving the smaller one of the two to the output.
Now we need to merge three sorted input arrays (A1, A2, and A3) of the same length into a (sorted) output array, and there are two methods:
Using the above Merge algorithm to merge A1 and A2 into A4, then using the same algorithm to merge A4 and A3 into the output array.
Revising the above Merge algorithm, by repeatedly comparing the smallest elements of the three input arrays, and moving the smallest one of the three to the output array.
Which of the above two algorithms is more efficient, if only considering the worst case of array element movements (i.e., assignments)?
Which of the above two algorithms is more efficient, if only considering the worst case of array element comparisons?
Between these two algorithms, which one has a higher overall efficiency in worst case?