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

Introduction to Mergesort

Overview of mergesort as a divide-and-conquer algorithm that recursively splits and merges sorted subarrays.

Introduction to Mergesort

What you'll learn: You'll discover how mergesort uses a divide-and-conquer strategy to efficiently sort data by breaking problems into smaller pieces.

The Big Idea

Mergesort takes a fundamentally different approach than the elementary sorts you've learned (bubble, selection, insertion). Instead of working through the array repeatedly or inserting elements one by one, mergesort divides the problem in half, conquers each half recursively, then merges the sorted halves back together.

Think of it like organizing a messy deck of cards: instead of trying to sort all 52 cards at once, you split them into two piles of 26, sort each pile separately, then carefully merge them back together by always picking the smaller top card from either pile.

How It Works

  1. Divide: Split your array into two roughly equal halves
  2. Conquer: Recursively sort each half (keep splitting until you have single elements)
  3. Merge: Combine the two sorted halves into one sorted array

The magic happens in the merge step: since both halves are already sorted, you can efficiently combine them by comparing elements from each side and building the final sorted result.

Why It Matters

Unlike bubble, selection, and insertion sort which struggle with large datasets, mergesort maintains consistent performance regardless of the input order. The divide-and-conquer approach breaks down seemingly overwhelming sorting tasks into manageable pieces—single elements are trivially sorted, and merging sorted lists is straightforward.

This recursive splitting continues until you reach the base case: a single element (which is already "sorted"). Then the algorithm works backward, merging pairs of sorted subarrays into larger sorted subarrays.

Key Takeaway: Mergesort is a divide-and-conquer algorithm that recursively splits an array in half, sorts each piece, and merges the sorted halves back together—trading the simplicity of elementary sorts for significantly better performance on larger datasets.