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

The Merge Operation

Learning how to merge two sorted subarrays into one sorted array using auxiliary space.

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

  1. Set up auxiliary space: Create a temporary array to hold the merged result
  2. Use three pointers: One for each input subarray and one for the output position
  3. Compare and copy: Look at the current element in each subarray, copy the smaller one to the output, and advance that subarray's pointer
  4. 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.