Introduction

The Merge Sorted Arrays problem involves combining two sorted arrays into a single sorted array.

Given two sorted arrays:

  • arr1[ ]
  • arr2[ ]

the task is to merge them while maintaining sorted order.

This problem helps in understanding:

  • Two Pointer Technique
  • sorted traversal
  • merging logic
  • efficient array processing

This concept is heavily used in:

 Merge Sort Algorithm

Example

Input:arr1[] = [1,3,5]
arr2[] = [2,4,6]
Output:
[1,2,3,4,5,6]
Explanation:
Elements from both arrays are merged
while maintaining sorted order.

Input:
arr1[] = [1,2,7]
arr2[] = [3,4,5]
Output:
[1,2,3,4,5,7]
Explanation:
Merged array remains sorted.

Constraints

 1 <= n,m <= 10^5 -10^9 <= arr[i] <= 10^9   Arrays are sorted

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Combine both arrays
  2. Sort the final array

This approach is easy to understand but sorting increases time complexity.

Steps

  1. Create a new array.
  2. Insert elements from first array.
  3. Insert elements from second array.
  4. Sort final array.
  5. Return merged array.

Dry Run

Input:arr1 = [1,3,5]
arr2 = [2,4,6]
Combine arrays:
[1,3,5,2,4,6]
Sort combined array:
[1,2,3,4,5,6]

Final Result:
[1,2,3,4,5,6]

Brute Force Code

Complexity Analysis

Time Complexity: O((n + m) log(n + m))Explanation:
Combined array is sorted.

Space Complexity: O(n + m)
Explanation:
Extra merged array is used.

Approach 2 : Optimized Solution (Two Pointer Technique)

Explanation

Since both arrays are already sorted, we can efficiently merge them using two pointers.

The idea is:

  1. Compare current elements of both arrays
  2. Insert smaller element into result
  3. Move corresponding pointer

This avoids unnecessary sorting.

Steps

  1. Initialize:
    • pointer i for arr1
    • pointer j for arr2
  2. Compare current elements.
  3. Insert smaller element into merged array.
  4. Move corresponding pointer.
  5. Insert remaining elements after traversal.

Dry Run

Input:arr1 = [1,3,5]
arr2 = [2,4,6]

Initially:
i = 0
j = 0

Compare:
1 and 2
1 is smaller

Merged:
[1]
Move i

Compare:
3 and 2
2 is smaller

Merged:
[1,2]
Move j
Continue traversal...

Final Result:
[1,2,3,4,5,6]

Optimized Code

Complexity Analysis

Time Complexity: O(n + m)Explanation:
Both arrays are traversed once.

Space Complexity: O(n + m)
Explanation:
Extra merged array is used.

Edge Cases

  1. One array is empty
  2. Both arrays contain duplicates
  3. Arrays contain negative numbers
  4. Arrays already merged
  5. Arrays contain one element

Why This Problem is Important

This problem helps in understanding:

  1. Two Pointer Technique
  2. Sorted traversal
  3. Merge logic
  4. Efficient array processing
  5. Partition-based algorithms

It is one of the most important array interview problems.

Real-World Applications

Merging techniques are used in:

  1. Merge Sort
  2. Database joins
  3. File merging systems
  4. Data synchronization
  5. Search engine indexing

Common Mistakes

  1. Forgetting remaining elements
  2. Incorrect pointer movement
  3. Wrong comparison logic
  4. Infinite loop conditions

Interview Tips

Interviewers often expect:

  1. O(n + m) solution
  2. Two Pointer optimization
  3. Proper merge explanation

Always explain why sorting again is unnecessary for already sorted arrays.

Related Questions

  1. Sort 0s,1s,2s
  2. Merge Intervals
  3. Two Sum
  4. Merge K Sorted Arrays
  5. Median of Two Sorted Arrays

Final Takeaway

The Merge Sorted Arrays problem is a fundamental two pointer problem that teaches efficient merging and sorted traversal techniques. Understanding this problem builds a strong foundation for advanced sorting and partition-based interview problems.