Question

Which sorting algorithm is based on the divide-and-conquer principle?

• A. Bubble Sort
• B. Selection Sort
• C. Merge Sort
• D. Insertion Sort

Hint:

The two most famous divide-and-conquer sorting algorithms are Merge Sort and Quick Sort. Both have an average time complexity of O(n log n).

Answer 1

The Correct Option is C

The divide-and-conquer principle is an algorithmic paradigm that involves three steps:
1. Divide: Break the problem into smaller subproblems of the same type. 2. Conquer: Solve the subproblems recursively. If the subproblems are small enough, solve them directly. 3. Combine: Combine the solutions of the subproblems to create a solution to the original problem.
Let's analyze the sorting algorithms:
(A) Bubble Sort, (B) Selection Sort, and (D) Insertion Sort are all iterative algorithms that do not follow the divide-and-conquer approach. They work by comparing and swapping adjacent elements or by finding the minimum/inserting an element in a sorted part of the array.
(C) Merge Sort: This algorithm is a classic example of divide-and-conquer. Divide: It divides the unsorted list into n sublists, each containing one element (which is considered sorted). Conquer: It repeatedly merges sublists to produce new sorted sublists. Combine: This merging step continues until there is only one sorted list remaining.
Quick Sort is another well-known sorting algorithm based on the divide-and-conquer principle.