Merge Two Sorted Arrays

Introduction

Merging two sorted arrays might seem tricky at first, but with a clear understanding and the right steps, it becomes a breeze. Whether you're working on a school project, preparing for an interview, or simply want to enhance your coding skills, mastering this skill is beneficial.

In programming, an array is a collection of items stored at contiguous memory locations. The items are easy to locate as they have specific indexes. But what if you have two sorted arrays and need to merge them? The key is to do it without disturbing the order of the elements.

Overview

This tutorial on how to merge two sorted arrays will guide you through the process of sorting arrays in several programming languages. We will focus on

• JavaScript
• Java
• Python

This will give a broad understanding of this important task.

We will also discuss a more challenging scenario - how to merge two sorted arrays without extra space.

So, whether you are using JavaScript, Java, or Python, this guide will help you become proficient in merging two sorted arrays with confidence.

Merge Two Sorted Arrays Javascript

JavaScript lacks a built-in function to merge two sorted arrays. However, we can write a simple function for this.

Code-

function merge(nums1, m, nums2, n) {
    let p1 = m - 1, p2 = n - 1, i = m + n - 1;
    while (p2 >= 0) {
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[i--] = nums1[p1--];
        } else {
            nums1[i--] = nums2[p2--];
        }
    }
}

let nums1 = [1,2,3,0,0,0];
let m = 3;
let nums2 = [2,5,6];
let n = 3;

merge(nums1, m, nums2, n);
console.log(nums1);

In this code, we use three-pointers. They are:

1. P1: p1 points to the end of the nums1 array (excluding the extra space)
2. P2: p2 points to the end of the nums2 array
3. I: I points to the position in nums1 where the next smallest number from the end will be placed

We compare the elements at p1 and p2 and place the larger one at position i in nums1. Then we move the pointer i and the pointer of the array from where the element was chosen one step back. We keep doing this until all the elements from nums2 have been placed correctly in nums1.

The output will be:

[1, 2, 2, 3, 5, 6]

Merge Two Sorted Arrays In Java

We can use ArrayList to merge two sorted arrays. Follow these steps to do so in Java-

Code-

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Integer[] a = {2,5,6,9};
        Integer[] b = {1,2,3,29};

        ArrayList<Integer> merged = mergeSortedArrays(a, b);

        for(int i : merged)
            System.out.print(i + " ");
    }

    public static ArrayList<Integer> mergeSortedArrays(Integer[] a, Integer[] b){
        ArrayList<Integer> merged = new ArrayList<>();

        int i = 0, j = 0;

        while (i < a.length && j < b.length) {
            if (a[i] < b[j])
                merged.add(a[i++]);
            else
                merged.add(b[j++]);
        }

        while (i < a.length)
            merged.add(a[i++]);

        while (j < b.length)
            merged.add(b[j++]);

        return merged;
    }
}

The function mergeSortedArrays takes two arrays a and b as input in this code. We start by declaring two pointers, i and j. This will help in keeping track of the current elements in a and b.

The first while loop runs as long as there are elements left in both a and b. We add a[i] if a[i] is less than b[j] to merge and increment i. Otherwise, we add b[j] to merge and increment j.

At least one of a or b will fully process after this loop. The remaining two while loops ensure that any elements left in a or b are added to the merge.

The output of this code will be 1 2 2 3 5 6 9 29.

How to Merge Two-Sorted Arrays Without Extra Space

Merging two sorted arrays without extra space is a bit tricky but doable. It's a problem often seen in technical interviews. The main challenge is to merge the arrays in a way that doesn't disturb their order while using constant space.

Here's how you can do it in C++ using the "gap" or "shell sort" method:

Code-

#include<bits/stdc++.h>
using namespace std;

int nextGap(int gap) {
    if (gap <= 1)
        return 0;
    return (gap / 2) + (gap % 2);
}

void merge(int *arr1, int *arr2, int n, int m) {
    int i, j, gap = n + m;
    for (gap = nextGap(gap); gap > 0; gap = nextGap(gap)) {
        for (i = 0; i + gap < n; i++)
            if (arr1[i] > arr1[i + gap])
                swap(arr1[i], arr1[i + gap]);
 
        for (j = gap > n ? gap-n : 0; i < n&&j < m; i++, j++)
            if (arr1[i] > arr2[j])
                swap(arr1[i], arr2[j]);
 
        if (j < m) {
            for (j = 0; j + gap < m; j++)
                if (arr2[j] > arr2[j + gap])
                    swap(arr2[j], arr2[j + gap]);
        }
    }
}

int main() {
    int a1[] = {10, 27, 38, 43, 82};
    int a2[] = {3, 9};
    int n = sizeof(a1) / sizeof(int);
    int m = sizeof(a2) / sizeof(int);

    merge(a1, a2, n, m);

    printf("First Array: ");
    for (int i=0; i<n; i++)
        printf("%d ", a1[i]);

    printf("\nSecond Array: ");
    for (int i=0; i<m; i++)
        printf("%d ", a2[i]);
    return 0;
}

In the merge function, arr1 and arr2 are the sorted arrays, and n and m are their respective sizes. The gap is initialized to the total size of n + m and then reduced by half in each iteration. The two for-loops compare elements gap distance apart and swap them if they're in the wrong order.

After running this code, the output will be two sorted arrays: 3, 9, 10, 27, 38, and 43, 82. Even though they're separate, together they represent the merged, sorted array.

Approach 1- Insertion Sort Approach

Insertion Sort is a clear sorting algorithm that constructs the final sorted array one item at a time. This method is simple and works well for smaller datasets. When applied to merging two sorted arrays, the idea is to treat one array as a sorted part and the other array as unsorted. For every element in the second array, we insert it in the correct position in the first array.

C++

Code-

#include<bits/stdc++.h>
using namespace std;

void merge(int arr1[], int arr2[], int n, int m) {
    int i = n - 1;
    int j = 0;

    while (i >= 0 && j < m) {
        if (arr1[i] > arr2[j])
            swap(arr1[i--], arr2[j++]);
        else
            break;
    }

    sort(arr1, arr1 + n);
    sort(arr2, arr2 + m);
}

int main() {
    int arr1[] = {1, 5, 9, 10, 15, 20};
    int arr2[] = {2, 3, 8, 13};
    int n = sizeof(arr1) / sizeof(int);
    int m = sizeof(arr2) / sizeof(int);

    merge(arr1, arr2, n, m);

    cout << "After Merging \nFirst Array: ";
    for (int i = 0; i < n; i++)
        cout << arr1[i] << " ";

    cout << "\nSecond Array: ";
    for (int i = 0; i < m; i++)
        cout << arr2[i] << " ";
    return 0;
}

Output-

Java

Code-

import java.util.Arrays;

public class Main {
    public static void merge(int[] arr1, int[] arr2, int n, int m) {
        int i = n - 1;
        int j = 0;

        while (i >= 0 && j < m) {
            if (arr1[i] > arr2[j]) {
                int temp = arr1[i];
                arr1[i] = arr2[j];
                arr2[j] = temp;
                i--; 
                j++;
            } else {
                break;
            }
        }

        Arrays.sort(arr1);
        Arrays.sort(arr2);
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 5, 9, 10, 15, 20};
        int[] arr2 = {2, 3, 8, 13};
        int n = arr1.length;
        int m = arr2.length;

        merge(arr1, arr2, n, m);

        System.out.print("After Merging \nFirst Array: ");
        for (int i = 0; i < n; i++)
            System.out.print(arr1[i] + " ");

        System.out.print("\nSecond Array: ");
        for (int i = 0; i < m; i++)
            System.out.print(arr2[i] + " ");
    }
}

Output-

Merge Two Sorted Arrays Python

Code-

def merge(arr1, arr2, n, m):
    i = n - 1
    j = 0


    while i >= 0 and j < m:
        if arr1[i] > arr2[j]:
            arr1[i], arr2[j] = arr2[j], arr1[i]
            i -= 1
            j += 1
        else:
            break


    arr1.sort()
    arr2.sort()


arr1 = [1, 5, 9, 10, 15, 20]
arr2 = [2, 3, 8, 13]
n = len(arr1)
m = len(arr2)


merge(arr1, arr2, n, m)


print("After Merging \nFirst Array:", arr1)
print("Second Array:", arr2)

Output-

Approach 2- Using Maps (O(mlog(m) + nlog(n)) Time and O(M+N) Extra Space)

This method is useful when working with maps (in C++ and Java) or dictionaries (in Python). Maps hold data sorted by key and combine two arrays. It operates at a time complexity of O(NlogN + MlogM). It offers a clear and concise way of merging the arrays without mutating the original data while using additional space (O(N+M)).

It’s particularly useful when you need to keep track of the element count.

C++

Code-

#include<bits/stdc++.h>
using namespace std;

void merge(int arr1[], int arr2[], int n, int m) {
    map<int, int> map;

    for (int i = 0; i < n; i++)
        map[arr1[i]]++;
    for (int i = 0; i < m; i++)
        map[arr2[i]]++;

    int i = 0;
    for (auto it = map.begin(); it != map.end(); ++it) {
        for (int j = 0; j < it->second; j++)
            arr1[i++] = it->first;
    }
}

int main() {
    int arr1[6] = {1, 5, 9, 10, 15, 20};
    int arr2[4] = {2, 3, 8, 13};
    int n = sizeof(arr1) / sizeof(int);
    int m = sizeof(arr2) / sizeof(int);

    merge(arr1, arr2, n, m);

    cout << "After Merging: ";
    for (int i = 0; i < n; i++)
        cout << arr1[i] << " ";
    return 0;
}

Output-

Java

Code-

import java.util.TreeMap;

public class Main {
    public static void merge(int[] arr1, int[] arr2, int n, int m) {
        TreeMap<Integer, Integer> map = new TreeMap<>();

        for (int i = 0; i < n; i++)
            map.put(arr1[i], map.getOrDefault(arr1[i], 0) + 1);
        for (int i = 0; i < m; i++)
            map.put(arr2[i], map.getOrDefault(arr2[i], 0) + 1);

        int i = 0;
        for (int key : map.keySet()) {
            int count = map.get(key);
            while (count-- > 0) {
                arr1[i++] = key;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 5, 9, 10, 15, 20};
        int[] arr2 = {2, 3, 8, 13};
        int n = arr1.length;
        int m = arr2.length;

        merge(arr1, arr2, n, m);

        System.out.print("After Merging: ");
        for (int i = 0; i < n; i++)
            System.out.print(arr1[i] + " ");
    }
}

Output-

Python

Code-

def merge(arr1, arr2, n, m):
    map = {}

    for i in range(n):
        map[arr1[i]] = map.get(arr1[i], 0) + 1
    for i in range(m):
        map[arr2[i]] = map.get(arr2[i], 0) + 1

    i = 0
    for key in sorted(map.keys()):
        count = map[key]
        while count > 0:
            arr1[i] = key
            i += 1
            count -= 1

arr1 = [1, 5, 9, 10, 15, 20]
arr2 = [2, 3, 8, 13]
n = len(arr1)
m = len(arr2)

merge(arr1, arr2, n, m)

print("After Merging: ", arr1)

Output-

1. We first create a map where the key is the array element and the value is its frequency.
2. We then loop over the sorted keys in the map and fill our target array with the proper number of each key.

This approach takes O(m log m + n log n) time due to the sorting and O(n + m) space to store the frequencies in the map.

Approach 3: Merge Sort

The merge sort-based solution is elegant and leverages a well-known sorting algorithm to perform the task. This method merges the arrays in O(N+M) time. It does require additional space for the merged result. It’s a good choice when you need a sorted array as the final output without preserving the original arrays.

Let's look at the third approach using Merge Sort for merging two sorted arrays in

1. C++
2. Java
3. Python

C++

Code-

#include<bits/stdc++.h>
using namespace std;

void merge(int arr1[], int arr2[], int n, int m) {
    int i = n - 1;
    int j = 0;

    while (i >= 0 && j < m) {
        if (arr1[i] > arr2[j])
            swap(arr1[i--], arr2[j++]);
        else
            break;
    }

    sort(arr1, arr1 + n);
    sort(arr2, arr2 + m);
}

int main() {
    int arr1[] = {1, 5, 9, 10, 15, 20};
    int arr2[] = {2, 3, 8, 13};
    int n = sizeof(arr1) / sizeof(int);
    int m = sizeof(arr2) / sizeof(int);

    merge(arr1, arr2, n, m);

    cout << "After Merging \nFirst Array: ";
    for (int i = 0; i < n; i++)
        cout << arr1[i] << " ";

    cout << "\nSecond Array: ";
    for (int i = 0; i < m; i++)
        cout << arr2[i] << " ";
    return 0;
}

Output-

Java

Code-

import java.util.Arrays;

public class Main {
    public static void merge(int[] arr1, int[] arr2, int n, int m) {
        int i = n - 1;
        int j = 0;

        while (i >= 0 && j < m) {
            if (arr1[i] > arr2[j]) {
                int temp = arr1[i];
                arr1[i] = arr2[j];
                arr2[j] = temp;
                i--; 
                j++;
            } else {
                break;
            }
        }

        Arrays.sort(arr1);
        Arrays.sort(arr2);
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 5, 9, 10, 15, 20};
        int[] arr2 = {2, 3, 8, 13};
        int n = arr1.length;
        int m = arr2.length;

        merge(arr1, arr2, n, m);

        System.out.print("After Merging \nFirst Array: ");
        for (int i = 0; i < n; i++)
            System.out.print(arr1[i] + " ");

        System.out.print("\nSecond Array: ");
        for (int i = 0; i < m; i++)
            System.out.print(arr2[i] + " ");
    }
}

Output-

Python

Code-

def merge(arr1, arr2, n, m):
    i = n - 1
    j = 0

    while i >= 0 and j < m:
        if arr1[i] > arr2[j]:
            arr1[i], arr2[j] = arr2[j], arr1[i]
            i -= 1
            j += 1
        else:
            break

    arr1.sort()
    arr2.sort()

arr1 = [1, 5, 9, 10, 15, 20]
arr2 = [2, 3, 8, 13]
n = len(arr1)
m = len(arr2)

merge(arr1, arr2, n, m)

print("After Merging \nFirst Array:", arr1)
print("Second Array:", arr2)

Output-

These examples show how you can merge two sorted arrays using the merge sort approach.

Conclusion

Merging two sorted arrays is an important skill that surfaces frequently in both academic and professional settings, notably in technical interviews and algorithm development. The three approaches—Insertion Sort Approach, Using Maps (or Dictionaries), and Merge Sort Approach—we have outlined in this tutorial provide different perspectives on handling this problem. Ultimately, deciding which approach to follow depends on the specific needs of the problem.

FAQs

1. How long does it take to merge two sorted arrays?

The time taken to merge two sorted arrays can vary based on the approach. For example, with the Insertion Sort approach, it's O(m*n), while with the Merge Sort approach, it's O(m+n).

2. How does the size of the arrays impact the choice of merging method?

For larger arrays, methods with lower time complexity, like merge sort, are usually more efficient. If memory is a concern, you might opt for in-place methods that don't need extra space.

3. What does 'in-place' merging mean?

'In-place' merging means that the operation is performed directly on the data structure without needing additional space.

4. What other data structures can be used to merge two sorted arrays?

Apart from arrays, we can also use structures like linked lists or binary heaps to merge sorted sequences.

5. How does Python's built-in 'merge()' function work?

Python's 'merge()' function is part of the 'heapq' module and merges multiple sorted inputs into a single sorted output (similar to 'sorted(itertools.chain(*iterables))').

6. What libraries in C++ can simplify the merging process?

The Standard Template Library (STL) in C++ provides a ‘merge()' function. You can use it to merge two sorted arrays.

7. Why merge two sorted arrays manually instead of using built-in functions?

Manual merging helps customize the process. It's handy when we want to handle duplicate elements in a special way.

8. How do I merge two sorted arrays in other languages, like Ruby or Swift?

The process is similar across languages.

• You can use the 'concat' method to combine arrays and the 'sort' method to sort them in Ruby.
• You can use the '+' operator to combine arrays and the 'sorted()' method to sort them in Swift.

9. How can we merge more than two sorted arrays?

You can use a priority queue (heap) to merge more than two sorted arrays at once.

10. How would the process change if the arrays were sorted in descending order instead of ascending order?

You need to adjust your comparison logic accordingly. Take the larger one instead of taking the smaller element first.