Merge Sort
Explore merge sort, a divide-and-conquer sorting algorithm that splits arrays recursively and merges sorted halves. Learn how it achieves O(n log n) time complexity and why it requires extra memory. This lesson helps you understand the algorithm's process, advantages, and limitations for sorting large datasets efficiently.
Imagine you have a large stack of exam papers sorted by student ID, but they got mixed up. Instead of trying to sort the whole stack in one go, you split it into smaller piles, sort those smaller piles, and then carefully merge them back together.
That is the main idea of merge sort. It breaks a big problem into smaller, identical problems, solves them recursively, and combines the results in order.
Merge sort is a divide-and-conquer sorting algorithm that recursively splits an array into smaller halves, sorts each half, and then merges the sorted halves into one final sorted array.
Core idea: Splitting is easy. The real work happens in the merge step, where two already sorted halves are combined into one sorted result.
How it works
Merge sort has two repeating phases. First, it splits the array until each piece is small enough to be trivially sorted. Then it merges those pieces in sorted order.
Divide: Split the array into two halves.
Conquer: Recursively sort each half.
Combine: Merge the two sorted halves into one sorted array.
Base case: An array of length 0 or 1 is already sorted, so the recursion stops there.
Interactive animation
The animation below highlights the recursive split-and-merge structure. It is not just about moving values around. It is about building sorted halves and then combining them.
Algorithm
Before writing Python, read through the algorithm and connect each step to the trace above.
If the list has one element or is empty:
It is already sorted, so return it.
Otherwise:
Divide the list into two halves:
Left half
Right half ...