Divide and Conquer

Merge sort uses a divide-and-conquer strategy: break the problem into smaller subproblems, solve them, then combine the solutions.

The Process

1. Divide: Split array into two halves
2. Conquer: Recursively sort each half
3. Combine: Merge the sorted halves

Visual Representation

Interactive Diagram

This interactive diagram requires JavaScript to be enabled.

Steps:

1. Divide array into two halves
2. Recursively divide each half
3. Continue until single elements (base case)

Recursive Structure

The algorithm recursively divides until it reaches the base case (single element or empty array), which is already sorted.

Base Case

When the array has 0 or 1 element, it’s already sorted. This is our stopping condition.

What’s Next?

Now that you understand how we divide, let’s learn how to merge the sorted halves back together.