The Merge Operation
What You'll Learn
You'll learn how to combine two already-sorted subarrays into a single sorted array—the key step that makes Mergesort work.
The Core Idea
Imagine you have two sorted stacks of numbered cards on a table. To combine them into one sorted stack, you'd compare the top cards, take the smaller one, and repeat. That's exactly what the merge operation does!
The merge operation takes two sorted subarrays and produces one sorted output array. Since both inputs are already sorted, we don't need to re-sort everything—we just compare elements from the front of each subarray and pick the smallest one at each step.
How It Works
- Set up auxiliary space: Create a temporary array to hold the merged result
- Use three pointers: One for each input subarray and one for the output position
- Compare and copy: Look at the current element in each subarray, copy the smaller one to the output, and advance that subarray's pointer
- Handle leftovers: When one subarray runs out, copy all remaining elements from the other subarray
For example, merging [1, 5, 9] and [2, 6, 7]:
- Compare 1 vs 2 → take 1
- Compare 5 vs 2 → take 2
- Compare 5 vs 6 → take 5
- Compare 9 vs 6 → take 6
- Compare 9 vs 7 → take 7
- Copy remaining 9
Result: [1, 2, 5, 6, 7, 9]
The operation is linear—it takes time proportional to the total number of elements being merged. Each element is examined exactly once.
Key Takeaway: The merge operation efficiently combines two sorted subarrays into one sorted array by repeatedly comparing their smallest unprocessed elements, requiring auxiliary space but running in linear time.