Merge 2 sorted arrays

Problem Statement

Given two sorted arrays, merge them into a single sorted array.

Constraints:

• Both arrays are already sorted in ascending order
• Arrays may have different sizes
• Elements may be duplicated

Example:

• Input: arr1 = [1, 3, 5, 7], arr2 = [2, 4, 6, 8]
• Output: [1, 2, 3, 4, 5, 6, 7, 8]

Example 2:

• Input: arr1 = [1, 1, 2], arr2 = [1, 3]
• Output: [1, 1, 1, 2, 3]

Approach 1: Brute Force (Concatenate and Sort)

Intuition

Simply concatenate both arrays and sort the result.

Algorithm

1. Create a new array of size m + n
2. Copy all elements from both arrays
3. Sort the combined array

import java.util.Arrays;

public class Solution {
    public int[] merge(int[] arr1, int[] arr2) {
        int[] result = new int[arr1.length + arr2.length];
        
        // Copy all elements
        int idx = 0;
        for (int num : arr1) {
            result[idx++] = num;
        }
        for (int num : arr2) {
            result[idx++] = num;
        }
        
        // Sort
        Arrays.sort(result);
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O((m+n) log(m+n)) - Sorting dominates
• Space Complexity: O(m+n) - Result array

Approach 2: Two Pointers (Optimal)

Intuition

Use two pointers, one for each array. Compare elements and add the smaller one to the result. This takes advantage of the fact that both arrays are already sorted.

Algorithm

1. Initialize two pointers i = 0, j = 0
2. While both pointers are within bounds:
   • Compare arr1[i] and arr2[j]
   • Add smaller element to result and advance that pointer
3. Add remaining elements from non-empty array

public class Solution {
    public int[] merge(int[] arr1, int[] arr2) {
        int m = arr1.length;
        int n = arr2.length;
        int[] result = new int[m + n];
        
        int i = 0, j = 0, k = 0;
        
        // Compare and merge
        while (i < m && j < n) {
            if (arr1[i] <= arr2[j]) {
                result[k++] = arr1[i++];
            } else {
                result[k++] = arr2[j++];
            }
        }
        
        // Copy remaining elements from arr1
        while (i < m) {
            result[k++] = arr1[i++];
        }
        
        // Copy remaining elements from arr2
        while (j < n) {
            result[k++] = arr2[j++];
        }
        
        return result;
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(m+n) - Each element visited once
• Space Complexity: O(m+n) - Result array

Approach 3: Merge into arr1 (In-place for LeetCode variant)

When arr1 has enough space to hold all elements.

public class Solution {
    public void merge(int[] arr1, int m, int[] arr2, int n) {
        int i = m - 1;      // Last element in arr1
        int j = n - 1;      // Last element in arr2
        int k = m + n - 1;  // Last position in merged array
        
        // Merge from the end
        while (i >= 0 && j >= 0) {
            if (arr1[i] > arr2[j]) {
                arr1[k--] = arr1[i--];
            } else {
                arr1[k--] = arr2[j--];
            }
        }
        
        // Copy remaining elements from arr2
        while (j >= 0) {
            arr1[k--] = arr2[j--];
        }
    }
}

Why Merge from End?

• If we merge from the start, we'd overwrite elements in arr1 before using them
• Merging from the end ensures we fill the empty spaces first
• No elements are overwritten before they're used

Complexity Analysis

• Time Complexity: O(m+n) - Each element visited once
• Space Complexity: O(1) - In-place merge

Merging K Sorted Arrays

Using Min-Heap

Complexity for K Arrays

• Time Complexity: O(N log K) where N is total elements
• Space Complexity: O(K) for the heap

Key Takeaways

1. Two Pointer Technique: Efficient for merging sorted arrays
2. Merge from End: When merging in-place to avoid overwriting
3. Stability: The merge is stable (maintains relative order of equal elements)
4. Foundation of Merge Sort: This is the merge step of merge sort
5. K-way Merge: Use min-heap for merging K sorted arrays
6. Applications: External sorting, database merge joins, stream processing