Codacoda
Back to Academy

patterns

Divide and Conquer

Divide and conquer breaks a problem into smaller, independent subproblems of the same type, solves each recursively, and combines the results. Classic examples include merge sort and binary search. The key insight is that combining solutions to subproblems is often more efficient than solving the original problem directly.

Use Cases

  • •Merge sort and quicksort algorithms
  • •Finding the closest pair of points in a plane
  • •Computing large exponents efficiently with fast power

Complexity Analysis

MetricBestAverageWorst
TimeO(n log n)O(n log n)O(n log n)
SpaceO(n)

Visualization

3827433982100123456
Speed:1x
Array: [38, 27, 43, 3, 9, 82, 10]. Merge sort using divide and conquer.Step 1 / 8

Implementation

Output

Click "Run Code" to see output...