Merge two sorted arrays
Ninja has been given two sorted integer arrays/lists ‘ARR1’ and ‘ARR2’ of size ‘M’ and ‘N’. Ninja has to merge these sorted arrays/lists into ‘ARR1’ as one sorted array. You may have to assume that ‘ARR1’ has a size equal to ‘M’ + ‘N’ such that ‘ARR1’ has enough space to add all the elements of ‘ARR2’ in ‘ARR1’.

For example:

‘ARR1’ = [3 6 9 0 0] ‘ARR2’ = [4 10] After merging the ‘ARR1’ and ‘ARR2’ in ‘ARR1’. ‘ARR1’ = [3 4 6 9 10]

Input Format

The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow. The first line of each test case contains two space-separated integers ‘M’ and ‘N’, which represent the size of ‘ARR1’ and ‘ARR2’. The next lines of each test case contain ‘M’ space-separated integers and ‘N’ zeros (i.e. 0) which represent the number of elements in ‘ARR1’. The next lines of each test case contain ‘N’ space-separated integers which represent the number of elements in ‘ARR2’.

Output Format :

For each test case, return the ‘ARR1’ after merging. Print the output of each test case in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Merge two sorted arrays

Ninja has been given two sorted integer arrays/lists ‘ARR1’ and ‘ARR2’ of size ‘M’ and ‘N’. Ninja has to merge these sorted arrays/lists into ‘ARR1’ as one sorted array. You may have to assume that ‘ARR1’ has a size equal to ‘M’ + ‘N’ such that ‘ARR1’ has enough space to add all the elements of ‘ARR2’ in ‘ARR1’.

For example:

‘ARR1’ = [3 6 9 0 0]
‘ARR2’ = [4 10]
After merging the ‘ARR1’ and ‘ARR2’ in ‘ARR1’. 
‘ARR1’ = [3 4 6 9 10]

Input Format

The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains two space-separated integers ‘M’ and ‘N’, which represent the size of ‘ARR1’ and ‘ARR2’.

The next lines of each test case contain ‘M’ space-separated integers and ‘N’ zeros (i.e. 0) which represent the number of elements in ‘ARR1’.

The next lines of each test case contain ‘N’ space-separated integers which represent the number of elements in ‘ARR2’.

Output Format :

For each test case, return the ‘ARR1’ after merging.

Print the output of each test case in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= ‘T’ <= 100
1 <= ‘M’, ‘N’ <= 5000
1 <= ‘ARR1[i], ARR2[i]’ <= 100000

Time Limit: 1 second

Accepted Answer

A simple approach would be to create a new arrays with size as sum of the sizes of both the arrays. Copy the elements of both the arrays in the new array and sort the array.
A space optimized approach also exists. While traversing the two sorted arrays parallelly, if we encounter the jth second array element is smaller than ith first array element, then jth element is to be included and replace some kth element in the first array.

Algorithm
1) Initialize i,j,k as 0,0,n-1 where n is size of arr1

2) Iterate through every element of arr1 and arr2 using two pointers i and j respectively
if arr1[i] is less than arr2[j]
increment i
else
swap the arr2[j] and arr1[k]
increment j and decrement k

3) Sort both arr1 and arr2

Accepted Answer

Brute Force

Our main task is that after merging ‘ARR2’ into ‘ARR1’. The resultant ‘ARR1’ is also sorted. So first we simply add all the elements of ‘ARR2’ into ‘ARR1’. Then we can apply any sorting algorithm to sort ‘ARR1’.

Algorithm:

We run a loop for ‘i’ = 0 to ‘N’:
- ‘ARR1[M + i]’ = ‘ARR2[i]’
Sort the array/list ‘ARR1’.
Finally, return ‘ARR1’.

Space Complexity: O(1)Explanation:

O(1) .

Because we are not using any extra space for finding our resultant answer.

Time Complexity: OtherExplanation:

O((M+N) * log(M+N)) Where ‘M’ and ‘N’ are the number of elements in ‘ARR1’ and ‘ARR2’ respectively.

First, we are traversing on ‘ARR2’ it takes O(N) time. Then we are sorting the ‘ARR1’. So the overall complexity is O((M+N) * log(M+N)).

C++ (g++ 5.4)

/*

	Time complexity: O((M+N) * log(M+N))

	Space complexity: O(1)



	Where M and N are the number of elements in ARR1 and ARR2 respectively.

*/



vector ninjaAndSortedArrays(vector& arr1, vector& arr2, int m, int n) {



	for (int i = 0; i < n; i++) {

		arr1[i + m] = arr2[i];

	}



	sort(arr1.begin(), arr1.end());

	return arr1;

}

Python (3.5)

'''
	Time complexity: O((M+N) * log(M+N))
	Space complexity: O(1)

	Where M and N are the number of elements in ARR1 and ARR2 respectively.
'''

def ninjaAndSortedArrays(arr1, arr2, m, n):
    
    for i in range(n):
        arr1[i + m] = arr2[i]
        
    arr1.sort()
    return arr1

Java (SE 1.8)

/*

	Time complexity: O((M+N) * log(M+N))

	Space complexity: O(1)



	Where M and N are the number of elements in ARR1 and ARR2 respectively.

*/



import java.util.Arrays;



public class Solution {

	public static int[] ninjaAndSortedArrays(int arr1[], int arr2[], int m, int n) {



		for (int i = 0; i < n; i++) {

			arr1[i + m] = arr2[i];

		}



		Arrays.sort(arr1);

		return arr1;



	}

}

Accepted Answer

Greedy Approach

As we know both ‘ARR1’ and ‘ARR2’ are sorted. So we can declare two variables ‘i’ and ‘j’ and initialize ‘i’ with ‘M’ and ‘j’ with ‘N’. Then we compare the last element of both arrays/lists and we insert the larger element to the end of the ‘ARR1’. We continue this process while all the elements of ‘ARR2’ are not merged into ‘ARR1’.

Algorithm:

We declare two variables ‘i’ and ‘j’ and initialize ‘i’ with ‘M’ and ‘j’ with ‘N’.
We declare a variable ‘LAST_INDEX’ and initialize it with ‘M+N’.
We run a loop while ‘j’ >= 0:
- If ‘i’ >= 0 and ‘ARR1[i]’ > ‘ARR2[j]’:
  - ‘ARR1[LAST_INDEX] = ‘ARR1[i]’
  - ‘i’--
- Else:
  - ‘ARR1[LAST_INDEX] = ‘ARR2[j]’
  - ‘j’--
- ‘LAST_INDEX’--
Finally, Return ‘ARR1’.

Space Complexity: O(1)Explanation:

O(1),

Because we are not using any extra space for finding our resultant answer.

Time Complexity: OtherExplanation:

O(M + N) Where ‘M’ and ‘N’ are the number of elements in ‘ARR1’ and ‘ARR2’ respectively.

Because we are traversing once on ‘ARR1’ and ‘ARR2’. So the overall complexity is O(M + N).