alleryStart learning →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.
Keep practising Algorithms
Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.