Divide and Conquer Visualization & Animation

Splits a problem into halves, solves each recursively, and combines results — basis of Merge Sort and Binary Search.

## What is it? Divide and Conquer is an algorithm design paradigm that solves a problem by splitting it into smaller sub-problems, solving each recursively, and combining the results. Merge Sort and Quick Sort are classic examples. ## How it works Three steps applied recursively: 1. **Divide** — split the problem into 2 (or more) smaller sub-problems of the same type 2. **Conquer** — solve each sub-problem recursively; base case is solved directly 3. **Combine** — merge/aggregate the sub-problem solutions to form the solution for the original problem Example (Merge Sort): - Divide array in half, sort each half, merge two sorted halves ## When to use - Sorting (Merge Sort, Quick Sort) - Searching (Binary Search) - Matrix multiplication (Strassen) - Finding the closest pair of points - Problems that can be expressed as "solve on left half + solve on right half + combine" ## Key Points - Often leads to O(n log n) algorithms where brute force is O(n²) - Recurrence relation: T(n) = 2T(n/2) + O(n) → O(n log n) by Master Theorem - Overhead of recursion and combining must be accounted for

Category: algorithms

Difficulty: intermediate

Time Complexity: O(n log n)

Space Complexity: O(log n)

Divide and Conquer

intermediate

Splits a problem into halves, solves each recursively, and combines results — basis of Merge Sort and Binary Search.

GFG
38
[0]
27
[1]
43
[2]
3
[3]
9
[4]
82
[5]
Left half
Right half
Combine
Inactive
Initial array.