Course contentsShow
← Computer Science
Lesson 753 of 2,87218. Sorting AlgorithmsFree lesson

The Divide-and-Conquer Strategy

Understanding how mergesort divides the array into halves until reaching base cases of single elements.

The Divide-and-Conquer Strategy

What you'll learn: How mergesort breaks down an array into single elements before building the sorted result back up.

The Core Idea

Divide-and-conquer is a problem-solving approach where you break a large problem into smaller, more manageable pieces, solve each piece independently, and then combine the solutions. In mergesort, this means:

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

Breaking Down to Base Cases

The "divide" phase continues recursively until you reach the simplest possible case: an array with just one element. A single-element array is already sorted by definition—there's nothing to arrange!

Think of it like organizing a messy deck of cards. Instead of trying to sort all 52 cards at once, you split the deck in half, then split each half again, and again, until you're holding individual cards. Each single card is "sorted." Now you can start combining pairs of cards in order, then combining those pairs, and so on, until the entire deck is organized.

The Recursive Pattern

For an array of size n:

  • First split: 2 subarrays of size n/2
  • Second split: 4 subarrays of size n/4
  • Continue splitting until you have n subarrays of size 1

Once you hit these base cases (single elements), the recursion stops diving deeper and begins the "combine" phase—merging sorted pieces back together.

Key Takeaway: Divide-and-conquer in mergesort recursively splits an array into halves until reaching base cases of single elements, which are trivially sorted and ready to be merged back together.