Merge Sort
Explore how merge sort breaks down large data sets into smaller parts, sorts each recursively, and merges them into a sorted slice. Understand its divide-and-conquer strategy, time and space complexity, and practical use cases to improve your sorting algorithm skills in Go.
We'll cover the following...
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 a slice into smaller halves, sorts each half, and then merges the sorted halves into one final sorted slice.
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 slice until each piece is small enough to be trivially sorted. Then it merges those pieces in sorted order.
Divide: Split the slice into two halves.
Conquer: Recursively sort each half.
Combine: Merge the two sorted halves into one sorted slice.
Base case: A slice 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 Go, read through the algorithm and connect each step to the trace above.
If the slice has one element or is empty:
It is already sorted, so return it.
Otherwise:
Divide the slice into two halves:
Left half
Right half ...