Merging two already-sorted arrays of total size n takes
AO(n) time, taking the smaller of the two fronts each step
BO(n²) time, comparing every pair
CO(n log n) time, since merge sort itself is n log n
DO(log n) time, using binary search on each pile
Answer & Solution
Correct answer: A. O(n) time, taking the smaller of the two fronts each step
The MERGE step touches each of the n elements exactly once, comparing fronts and emitting the smaller. Linear time in the combined size. Binary-search-based merging exists but the standard merge runs O(n). The n² and n log n options confuse merging (which is just the combine step) with the full sort.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for