Course contentsShow
← Computer Science
Lesson 256 of 2,8726. Arrays and Basic CollectionsFree lesson

Merging Two Sorted Arrays

Combine two sorted arrays into one sorted result using two-pointer merge technique in O(n+m) time.

Merging Two Sorted Arrays

What you'll learn: How to efficiently combine two already-sorted arrays into a single sorted array without re-sorting everything.

The Core Idea

Imagine you have two stacks of graded test papers, each already sorted by score from lowest to highest. To merge them into one sorted stack, you don't need to shuffle and re-sort everything. Instead, you compare the top papers from each stack and always take the smaller one, placing it on your new merged stack. Repeat until both stacks are empty.

This is the two-pointer merge technique: you maintain an index (pointer) for each sorted array, comparing elements at those positions. You copy the smaller element to your result array and advance that pointer. Continue until you've processed all elements from both arrays.

Why This Matters

This technique runs in O(n + m) time, where n and m are the lengths of the two arrays. You visit each element exactly once—no nested loops, no re-sorting. It's the same efficient merge used in Merge Sort algorithms.

The Process

  1. Create a result array large enough to hold all elements from both arrays
  2. Start with pointers at the beginning of each array (both at index 0)
  3. Compare elements at both pointers
  4. Copy the smaller element to the result, advance that pointer
  5. When one array is exhausted, copy remaining elements from the other

If arrays have different lengths, remember to handle leftover elements after one pointer reaches the end.

Key Takeaway: The two-pointer merge technique efficiently combines two sorted arrays in linear time by comparing front elements and always taking the smaller one, leveraging the existing sorted order.