Merge two sorted arrays

Given two sorted arrays, the task is to merge them into a single sorted array. The two arrays may have different sizes, and the merged array should maintain the sorted order.

Input-Output Examples

Example 1:

  • Input:
    • Array1: [1, 3, 5, 7]
    • Array2: [2, 4, 6, 8]
  • Output: [1, 2, 3, 4, 5, 6, 7, 8]

Example 2:

  • Input:
    • Array1: [5, 10, 15]
    • Array2: [3, 8, 12]
  • Output: [3, 5, 8, 10, 12, 15]

Approach:

To merge two sorted arrays into one sorted array, we can use the two-pointer technique. This method efficiently merges the arrays with a time complexity of O(n + m), where n and m are the sizes of the two arrays.

Steps to implement:

  1. Initialize two pointers, one for each array, starting at the beginning of the arrays.
  2. Compare the elements at these pointers.
  3. Append the smaller element to the merged array and move the corresponding pointer to the next element.
  4. Repeat steps 2 and 3 until one of the pointers reaches the end of its array.
  5. Append the remaining elements of the other array to the merged array.

Technique to be used: Two-pointer technique

C++ Program to merge two sorted arrays

cpp
#include <iostream>
#include <vector>
using namespace std;

vector<int> mergeSortedArrays(vector<int>& arr1, vector<int>& arr2) {
    int n1 = arr1.size();
    int n2 = arr2.size();
    vector<int> mergedArray;
    int i = 0, j = 0;
    
    // Merge arrays until one of them is exhausted
    while (i < n1 && j < n2) {
        if (arr1[i] < arr2[j]) {
            mergedArray.push_back(arr1[i++]);
        } else {
            mergedArray.push_back(arr2[j++]);
        }
    }
    
    // Add remaining elements of arr1
    while (i < n1) {
        mergedArray.push_back(arr1[i++]);
    }
    
    // Add remaining elements of arr2
    while (j < n2) {
        mergedArray.push_back(arr2[j++]);
    }
    
    return mergedArray;
}

int main() {
    vector<int> arr1 = {1, 3, 5, 7};
    vector<int> arr2 = {2, 4, 6, 8};
    vector<int> result = mergeSortedArrays(arr1, arr2);
    
    cout << "Merged array: ";
    for (int num : result) {
        cout << num << " ";
    }
    return 0;
}

Java Program to merge two sorted arrays

java
import java.util.ArrayList;
import java.util.List;

public class MergeSortedArrays {
    public static List<Integer> mergeSortedArrays(int[] arr1, int[] arr2) {
        int n1 = arr1.length;
        int n2 = arr2.length;
        List<Integer> mergedArray = new ArrayList<>();
        int i = 0, j = 0;
        
        // Merge arrays until one of them is exhausted
        while (i < n1 && j < n2) {
            if (arr1[i] < arr2[j]) {
                mergedArray.add(arr1[i++]);
            } else {
                mergedArray.add(arr2[j++]);
            }
        }
        
        // Add remaining elements of arr1
        while (i < n1) {
            mergedArray.add(arr1[i++]);
        }
        
        // Add remaining elements of arr2
        while (j < n2) {
            mergedArray.add(arr2[j++]);
        }
        
        return mergedArray;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5, 7};
        int[] arr2 = {2, 4, 6, 8};
        List<Integer> result = mergeSortedArrays(arr1, arr2);
        
        System.out.println("Merged array: " + result);
    }
}

Python Program to merge two sorted arrays

python
def merge_sorted_arrays(arr1, arr2):
    n1, n2 = len(arr1), len(arr2)
    merged_array = []
    i, j = 0, 0
    
    # Merge arrays until one of them is exhausted
    while i < n1 and j < n2:
        if arr1[i] < arr2[j]:
            merged_array.append(arr1[i])
            i += 1
        else:
            merged_array.append(arr2[j])
            j += 1
    
    # Add remaining elements of arr1
    while i < n1:
        merged_array.append(arr1[i])
        i += 1
    
    # Add remaining elements of arr2
    while j < n2:
        merged_array.append(arr2[j])
        j += 1
    
    return merged_array

# Example usage
arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]
result = merge_sorted_arrays(arr1, arr2)
print("Merged array:", result)

DSA

5510

885

Related Articles