Merge Sorted Array

Code Crafter
Published : 04 February 2024

184 Views

Array Sorting Coding Problems Low Two Pointes

You are given two integer arrays arr1 and arr2 sorted in accending order and two integers m and n representing the number of elements in arr1 and arr2 respectively. size of arr1 is m+n.

Merge arr1 and arr2 into a single array (arr1) sorted in accending order.

Example 1

Input : arr1 = [4, 8, 13, 25, 0, 0], m = 4, arr2 = [2, 23], n = 2

Output : [2, 4, 8, 13, 23, 25]

Constraints : -

arr1.length == m + n
arr2.length == n
1 <= m + n <= 200
0 <= m, n <= 200
-109 <= arr1[i], arr2[j] <= 109

Brute Force Approach

Copy all elements of arr2 into the unused space of arr1.
Sort the entire arr1 array.

C++

Java

Python

#include <iostream>
#include <vector>
#include <algorithm>

void merge(std::vector<int>&amp; arr1, int m, const std::vector<int>&amp; arr2, int n) {
    for (int i = 0; i < n; ++i) {
        arr1[m + i] = arr2[i];
    }
    std::sort(arr1.begin(), arr1.end());
}
int main() {
    std::vector<int> arr1 = {1, 3, 5, 0, 0, 0}; // extra space for arr2
    std::vector<int> arr2 = {2, 4, 6};
    int m = 3;
    int n = 3;
    merge(arr1, m, arr2, n);
    std::cout << "Merged array: ";
    for (int num : arr1) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

Merged array: [1, 2, 3, 4, 5, 6]

⏱️ Time Complexity : O((m + n) log(m + n))

🧪 Space Complexity : O(1)

Merge Using Extra Space

Use a new array and merge like in merge sort
Compare elements from both arrays and place the smaller one in the result
Finally, copy merged array back to arr1

C++

Java

Python

#include <iostream>
#include <vector>
#include <algorithm>

void merge(std::vector<int>&amp; arr1, int m, const std::vector<int>&amp; arr2, int n) {
    std::vector<int> merged(m + n);
    int i = 0, j = 0, k = 0;
    while (i < m &amp;&amp; j < n) {
        if (arr1[i] <= arr2[j]) {
            merged[k++] = arr1[i++];
        } else {
            merged[k++] = arr2[j++];
        }
    }
    while (i < m) merged[k++] = arr1[i++];
    while (j < n) merged[k++] = arr2[j++];
    for (int l = 0; l < m + n; l++) {
        arr1[l] = merged[l];
    }
}

int main() {
    std::vector<int> arr1 = {1, 3, 5, 0, 0, 0}; // size = m + n
    std::vector<int> arr2 = {2, 4, 6};
    int m = 3, n = 3;
    merge(arr1, m, arr2, n);
    std::cout << "Merged Array: ";
    for (int num : arr1) std::cout << num << " ";
    std::cout << std::endl;
    return 0;
}

Merged Array: [1, 2, 3, 4, 5, 6]

⏱️ Time Complexity : O(m + n)

🧪 Space Complexity : O(m + n)

🚀 Optimal In-Place Approach: Two-Pointer from the End

Work backwards from the end of arr1.
Start comparing from m-1 and n-1 and place the largest element at m+n-1 position.
Avoids extra space and works in-place

C++

Java

Python

Java Script

#include <iostream>
#include <vector>

void merge(std::vector<int>&amp; arr1, int m, const std::vector<int>&amp; arr2, int n) {
    int i = m - 1;
    int j = n - 1;
    int k = m + n - 1;
    while (i >= 0 &amp;&amp; j >= 0) {
        if (arr1[i] > arr2[j]) {
            arr1[k--] = arr1[i--];
        } else {
            arr1[k--] = arr2[j--];
        }
    }
    while (j >= 0) {
        arr1[k--] = arr2[j--];
    }
}

int main() {
    std::vector<int> arr1 = {1, 3, 5, 0, 0, 0};
    std::vector<int> arr2 = {2, 4, 6};
    int m = 3;
    int n = 3;
    merge(arr1, m, arr2, n);
    std::cout << "Merged Array: ";
    for (int num : arr1) std::cout << num << " ";
    std::cout << std::endl;
    return 0;
}

Merged Array: [1, 2, 3, 4, 5, 6]

⏱️ Time Complexity : O(m + n)

🧪 Space Complexity : O(1)

Complexity Table

Approach	Time Complexity	Space Complexity	Key Idea	Notes
Brute Force	O((m+n) log(m+n))	O(1)	Copy and sort	Simple but inefficient
Extra Space Merge	O(m + n)	O(m + n)	Merge into a third array	Better but uses space
In-Place Optimal	O(m + n)	O(1)	Merge from the back using two-pointers	Best approach