How to Merge Two Sorted Arrays Into a Sorted Array?

Have you ever wondered how we effectively manage to arrange elements in a certain symmetrical order?

Let us give you a few examples to understand this better:

• The assortment of fruits on tray
• Arranging eggs in a basket
• Chocolates arranged within a box

All of these arrangements seem to be near perfect and without a flaw.

How is this possible?

Well, the use of arrays in real life persists in almost every real-time situation and it is larger than we can imagine or comprehend.

Using the programming logics and algorithms, we can even manipulate the computer programs to arrange elements in a certain order.

This is essentially how the function of merging the arrays in a computer program works.

With that said, learn the functions to merge two sorted arrays and its implications in the blog.

What are Sorted Arrays?

Arrays in Java programming are an effective method for storing elements from a series of data that belong to a similar category.

Did you know?

 Arrays.sort() function in Java provides access to pre-sorting functions. This is a class in Java which is essentially a static method meaning that it returns absolutely no value.

When a programmer calls/invokes the sorting function in Java, the program scans through each of the elements contained within the array. It can effectively sort the data into either an ascending or a descending order.

An array in Java can be of the following data types:

• float
• char
• long
• int

Check out the detailed analysis of the sorting function in Array as follows:

(int[] ar, int from_index, int to_index)

• Here in the above syntax, we can observe that ar, represents the name of the array.
• The from_index essentially denotes the point where the sorting function starts.
• Similarly, the to_index denotes the point where the sorting function comes to an end.

Now that you have a general idea on how the sorting function for an array is invoked in Java, let us discuss what are some of the common uses of sorting an array in Java.

What are the uses of sorting arrays in Java?

Sorting in Java fundamentally defines how the elements can be arranged in a certain order as per the requirement of the program.

Now, the arrays in Java are essentially sorted for mainly two reasons:

For numerical sorting

Well, as the term suggests, once the sorting function gets invoked in Java for a numerical series of data, we can expect the array to get sorted in either an ascending or a descending order.

For lexical sorting

Lexical sorting or sorting a data lexicographically, essentially means to sort the array alphabetically. Again, this alphabetical sorting can either be in ascending or descending order of characters.

Either way, sorting an array gives the program a better edge at performing other functions efficiently such as merging two sorted arrays, which we shall be discussing below.

What methods to use for merging two sorted arrays into a single sorted array?

For the process of merging two sorted arrays, we essentially have four different methods that we will be discussing shortly.

But, before we get into that, let’s discuss the type of problem statement that you will encounter in terms of merging two sorted arrays.

Problem Statement

You have been given two different sorted arrays. Merge them together such that they appear in a sorted order by the end of the program.

Example:

Input: arr1[] = {2,3,4,5}, arr2[] = {6,7,8,9}

Output: arr3[] = {2,3,4,5,6,7,8,9}

Seeing the above example, there are four different approaches with their respective time and space complexities that can be revoked to solve this entire problem statement.

Let’s find out what is the process of their implementation and how their algorithms work.

Method 1: Applying the Brute Force Algorithm

This is definitely one of the most effective and efficient methods. When the Brute Force function is revoked, you will find that the problem will start dividing itself into smaller subsets until the output is attained. The Brute Force Algorithm is also effective for solving problems based on string compression in Java.

Here’s how the algorithm for the Brute Force method would work:

• The contents of arr1[] will be entered into a third array i.e arr3.

• Next up, the contents of arr2[] shall be considered and entered into the third array.

• Finally, the third array will be sorted and after the merging process is completed, the algorithm will sort itself out.

Time Complexity for this approach:

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

Method 2: Reducing Time Complexity from the first approach

In this method we will be implementing O(n1+n2) extra space.

Let’s find out how the algorithm for this approach will be executed:

• You can begin with creating a third array i.e arr3 of size n1+n2.

• Next up, you can copy all the n1 elements from the first array i.e arr1[] to the newly created array.

• Perform the same function with the third array and print the results.

Time Complexity for this approach:

O(n1*n2)

Method 3: Using the Merge Sort Algorithm

The Merge Sort is a function available in Java which allows the program to sort the problem by itself by using a simple class that is expressed as follows:

Merge[]

Here’s how the merge sort algorithm will be executed in the program:

• Start by creating an array of size n1 + n2. Let’s name this array arr3[].

• Simultaneously, keep traversing the first and second arrays i.e arr1 and arr2.

• Next up, start allocating the elements from the first and second arrays into the third array in an increasing order of value.

• If you find that there are certain elements remaining, copy them all in the third array.

Time Complexity for this approach:

(O(n1 +n2)

Final Thoughts

According to the statistics nearly 90% of 2.8 billion global companies use Arrays in Java for their go-to programme solutions.

This is how important it is to learn development and programming in Java along with its basic concepts (such as Arrays) for a fresher who is seeking a job in this field.

If you are interested in more blogs on coding fundamentals such as DSA, OOPs or string compression, then do check out some of the other blogs that we have created on these topics.