Question

Choose the pair of sorting algorithms using divide and conquer strategy.

• A. Bubble Sort, Quick Sort
• B. Merge Sort, Quick Sort
• C. Merge Sort, Bucket Sort
• D. Bubble Sort, Selection Sort

Hint:

Common Divide and Conquer Algorithms:
• Merge Sort
• Quick Sort
• Binary Search
• Strassen Matrix Multiplication

Answer 1

The Correct Option is B

Concept: Divide and Conquer is an algorithm design strategy that works in three phases:
• Divide the problem into smaller subproblems.
• Solve the subproblems recursively.
• Combine the solutions. Many efficient sorting algorithms are based on this technique.

Step 1: Analyze Merge Sort.
Merge Sort divides the array into two halves repeatedly. After sorting the halves recursively, they are merged. Thus it follows: \[ \text{Divide} \rightarrow \text{Conquer} \rightarrow \text{Combine}. \] Hence Merge Sort uses Divide and Conquer.

Step 2: Analyze Quick Sort.
Quick Sort selects a pivot element and partitions the array. The left and right partitions are recursively sorted. Thus Quick Sort also follows Divide and Conquer.

Step 3: Examine other algorithms.
Bubble Sort and Selection Sort do not use Divide and Conquer. They use iterative comparison techniques. Therefore those options are incorrect.

Step 4: Write the answer.
The pair using Divide and Conquer is \[ \boxed{\text{Merge Sort and Quick Sort}}. \] Hence option (B) is correct.