Merge Two Sorted Arrays

Problem Statement

Given two sorted integer arrays of size m and n, Your task is to merge both the given sorted arrays into one so that the output array is also sorted.

The image below visualises the merge two sorted arrays problem.

The constraints for the merge two sorted arrays problem are given below.

Example

Input:

Output:

Approach-1: Naive Approach

In the naive approach, we insert all the elements from nums1[] and nums2[] into a new array nums3[] and, finally, sort it to get a sorted merge array.

Implementation (C++, Java, Python)

Let's examine the code for the insertion sort approach in Java, Python, and C++.

C++ Implementation

Output:

Java Implementation

Output:

Python Implementation

Output:

Complexity Analysis :

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

Space Complexity: O(m+n)

Approach - 2: Insertion Sort Approach

In the Insertion Sort approach of the merge two sorted arrays problem, we make an array nums3[] of size $m+n$ and insert all the elements of input array nums1[] in the array nums3[] and then insert every element of nums2[] by applying insertion sort to get the sorted array as an output.

Algorithm:

1. Create an array of size $m+n$ named nums3[].
2. Copy all elements of nums1[] to nums3[].
3. Now traverse the elements of nums2[] and insert elements one by one to nums3[] by using the insertion sort.

Implementation (C++, Java, Python)

Let's examine the code for the insertion sort approach in Java, Python, and C++.

C++ Implementation

Output:

Java Implementation

Output:

Python Implementation

Output:

Complexity Analysis :

Time Complexity: $O(m*n)$ .

Space Complexity: $O(m+n)$.

Approach - 3 : Merge Sort

In the Merge Sort approach of the merge sorted arrays problem, we merge elements of two input sorted arrays using the merge sort algorithm. In merge sort, we traverse both input arrays simultaneously and apply a merge sort algorithm to get sorted resultant arrays.

Algorithm:

1. Create an array nums3[] of size $m + n$ to store the resultant sorted array.
2. Start simultaneously traversing both input array nums1[] and nums2[].
3. Choose a current smaller element from nums1[] and nums2[] and copy this element to nums3[] and increment the pointer of nums3[] and the array whose elements you have chosen.
4. If there are elements left in nums1[] or nums2[], then copy all the left elements to nums3[].

Implementation (C++, Java, Python)

Let's examine the code for the merge sort approach in Java, Python, and C++.

C++ Implementation

Output:

Java Implementation

Output:

Python Implementation

Output:

Complexity Analysis

Time Complexity: $O(m+n)$.

Space Complexity: $O(m+n)$.

To learn how to merge two sorted arrays without extra space, refer to Merge Two Sorted Arrays Without Extra Space.

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

In this approach, we use a map to store the values of both the input array and the output array, and then we print the map's keys to get sorted elements as an output.

Algorithm:

1. Create an empty map.
2. Traverse both input arrays individually and store the array element as a key in the map.
3. Then, print the key set of the map.

Implementation (C++, Java, Python)

Let us see code in C++, Java, Python

C++ Implementation

Output:

Java Implementation

Output:

Python Implementation

Output:

Complexity Analysis

Time Complexity: The time complexity of this approach is $O(mlogm + nlogn)$.

Space Complexity: $O(m+n)$

Explore Scaler Topics Data Structures Tutorial and enhance your DSA skills with Reading Tracks and Challenges.