The Merge Sort algorithm is based on which of the following design approaches?
The Merge Sort algorithm is based on which of the following design approaches?
Answer: D. Divide and Conquer — Why Merge Sort is a divide-and-conquer algorithm Key idea: break the problem into smaller subproblems, solve each recursively, and combine the results.…
- A.
Greedy approach
- B.
Backtracking
- C.
Dynamic programming
- D.
Divide and Conquer
Attempted by 1065 students.
Show answer & explanation
Correct answer: D
Why Merge Sort is a divide-and-conquer algorithm
Key idea: break the problem into smaller subproblems, solve each recursively, and combine the results.
Divide: Split the list into two roughly equal halves.
Conquer: Recursively sort each half using the same method.
Combine: Merge the two sorted halves into a single sorted list.
Time complexity: O(n log n) in best, average, and worst cases.
Space complexity: O(n) auxiliary space for the merge process (unless using an in-place variant with additional complexity).
Note: This differs from greedy algorithms (which make local optimum choices), backtracking (which explores and abandons partial solutions), and dynamic programming (which relies on overlapping subproblems and memoization). Merge Sort’s structure—divide, recurse, and merge—is the hallmark of the divide-and-conquer approach.