The Merge Operation

Merging is the key operation in merge sort. It combines two sorted arrays into one sorted array.

How Merging Works

Use two pointers, one for each array. Compare elements and add the smaller one to the result.

Step-by-Step Example

Merge [2, 5, 8] and [1, 3, 9]:

1. Compare 2 and 1 → 1 is smaller, add to result: [1]
2. Compare 2 and 3 → 2 is smaller, add to result: [1, 2]
3. Compare 5 and 3 → 3 is smaller, add to result: [1, 2, 3]
4. Compare 5 and 9 → 5 is smaller, add to result: [1, 2, 3, 5]
5. Compare 8 and 9 → 8 is smaller, add to result: [1, 2, 3, 5, 8]
6. Add remaining 9: [1, 2, 3, 5, 8, 9]

Implementation

Key Points

1. Two pointers: One for each array
2. Compare: Always compare current elements
3. Add smaller: Add the smaller element to result
4. Advance pointer: Move pointer of array we took from
5. Add remaining: When one array is done, add rest of other

Time Complexity of Merge

Merging two arrays of size n/2 takes O(n) time. We visit each element once.

What’s Next?

Now that you understand merging, let’s see the complete merge sort algorithm in action.