Merge two sorted arrays

If you are here practicing arrays for technical interviews, we should share an important piece of information that arrays are one of the most common coding problems asked during interviews.

One such common array problem that we will be tackling today is merging two sorted arrays. Arrays are always lexically aligned within a program.

This means that they are arranged in a chain-like structure due to which the arrays make it extremely easier to combine two or more arrays within a program.

In this blog, we are going to be discussing a few approaches to merge two sorted arrays in a program.

We will start by considering the smallest elements from the input arrays and move onto the rest of the elements.

Further, we will also discuss how you can reduce the time complexities of the functions to variable lengths.

Let's learn how you can effectively merge two given sorted arrays in minimal steps.

What are Sorted Arrays?

We are all familiar with the fact that Array data structures are arranged in a lexical order. This means that the data or elements stored within an array are arranged in the sequence of a chain.

Arrays are widely used for storing elements such as words, numbers, single alphabets and even symbols.

Whether these elements are arranged in a sorted order or not, while storing the data it becomes difficult to keep track of the elements.

To help tackle this issue while running a program, the sort[] function allows us to sort the elements contained within the array in either ascending or descending orders.

We can sort the array data structures in the following formats:

• Numerically

In this way we are sorting the array from either 1-100 or 100-1

• Alphabetically

In this context, the elements will be arranged from either a-z or z-a

Now, the problem of sorting and merging two sorted arrays is a common coding problem that is often encountered in technical interviews.

In our next section, we are finding the different methods that are useful for solving this programming problem.

How to merge two sorted arrays?

Before we discuss the approaches, let us consider a problem statement that you might notice during your technical interviews.

Problem Statement

You have been provided two different sorted arrays. You are required to merge them in such an order that they remain sorted while deriving the output.

Input: arr1[] = {5,6,7,8} arr2[] = {10,11,12,13}

Output: arr3[] = {5,6,7,8,10,11,12,13}

Answer Key

One of the most efficient approaches that can be applied to merge two sorted arrays would be using the Brute Force Algorithm.

Method 1: Using Brute Force Algorithm

The Brute Force is a common algorithm that is radically used for solving a number of different coding problems. This algorithm essentially tries to figure out all the possible solutions to a problem so that it can attain the required output.

• In the context of this problem, the algorithm will start with taking all the elements from arr1 and arr2.

• Afterwards, it will simply sort the third array i.e arr3

Here's an implementation of the Brute Force Algorithm for this problem:

• Start by running the driver code for the program

• Next up, we will be forming a third array i.e arr3 that will be used for storing all the elements from the first and the second arrays

• Next up, start traversing the first array i.e arr1 and insert all of its elements into arr3

• Perform the same action for arr2 and also insert all of its elements into arr3

• Run the sort[] function for arr3 to complete the program

Time Complexity for this approach:

O((m+n) log(m+n)) where, the size of the third array is m+n

Method 2: By initialising (O(n1*n2) Time and O(n1+n2) Space Complexities

For this approach we will consider reducing the time and space complexities of the program so that we can attain our desired output faster than the last approach.

Here's how the algorithm for this would function:

• Start by forming a third array of the size n1+n2

• Now, start copying all the elements from n1 i.e the first array into the third array or arr3

• Also traverse the second array and copy all the n2 elements into arr3

• You can use the insertion sort[] function for copying each element one by one into the third array

Time Complexity for this approach:

O(n1*n2)

Method 3: By reducing O(n1*n2) Time Complexity itno (O(n1+n2)

In order to reduce the time complexity of this approach to (O(n1+n2), the idea here is to initialize the merge sort algorithm or the merge sort function in the program.

Here are the algorithms for this approach:

• Start by forming a third array. Name it as arr3, this array will be of n1+n2 size

• Now, start traversing both the first and the second input arrays at the same time

• Check whether your current element within the first array is relatively smaller than the second element of the array

• If yes, then store the elements from the first array and increment its value in the first array

• Perform the same functions for the second array until all elements have been considered

• Now, store all the elements from the first array i.e arr1

• Also start incrementing all the elements from the second array i.e arr2

• Finally, go ahead and copy all the rest of the elements or the remaining elements from both the input arrays into arr3

• Run the driver code to test your program and print the output

Time Complexity for this approach:

(O(n1+n2)

Wrapping Up

The Brute Force is an extremely versatile algorithm that can be applied for solving all forms of programming problems such as count distinct elements in every window.

If you are interested in learning about more such approaches for solving coding problems, we would recommend having a look at other coding blogs on our website.