Merge Two Sorted Integer Arrays in Linear Time

Given two sorted integer arrays, return a third array consisting of elements of both first and second arrays in a sorted manner.

Example:

Input Array 1: {1, 2, 3}
Input Array 2: {4, 5, 6}          
Output Array: {1, 2, 3, 4, 5, 6}

Need a hand? Try out these hints, one at a time.

Quick hint to get things rolling

The key here is to use merge sort to create the resultant array.

Final hint! You should be able to code the problem on viewing this.

1. Declare and initialize 3 counters to 0 to keep track of the positions of input Array 1, 2 and the output array.

2. Start a loop to traverse through the elements of input Array 1 and 2. Make sure it runs till either of position counters are less than the size of the respective arrays.

3. Compare the elements at the current positions in input Array 1 and Array 2. Insert the smaller element to the output array and increment the position counters of respective arrays by 1.

4. At the end of the loop, insert all the left over elements from the input arrays to the output array as is.

5. Return the output array. This has all the elements from both the input arrays in a sorted manner.

public static int[] mergeSortedArrays(int[] inputSortedArray1, int [] inputSortedArray2) {
    


}

This Coding Interview Question is available with an answer in the following programming languages :

Java

Python

Merge Two Sorted Integer Arrays in Linear Time

Quick hint to get things rolling

Final hint! You should be able to code the problem on viewing this.

The interview prep tool you'll fall in love with!

This Coding Interview Question is available with an answer in the following programming languages :