How to Merge Two Sorted Arrays in C

From managing databases to creating compilers, the C programming language has a vast range of uses even though it is considerably older than the other programming languages.

In the context of the other programming languages, did you know that the C programming language was used for developing a range of other languages such as Java, C++, and Python?

This is why it is highly recommended to learn C, especially for beginners who are new to programming.

Well in order to get a stronghold in learning C programming, it is important to solve problems using this coding language.

In this blog, we will be discussing the algorithms and their implementations for merging two sorted arrays using C.

Learn how C programming is different from the other programming languages and how the functions are implemented in various forms in C programming.

What Do You Mean by Merging Two Sorted Arrays in C?

Arrays are essentially lexically aligned series of data that are used for storing elements such as numbers, alphabets, symbols, or other forms of data.

There are a number of different functions that are performed using arrays; one such function is merging two different sorted arrays.

The process of merging two sorted arrays in C programming is quite similar to combining or concatenating two arrays within a single array.

For instance, if a certain array has 3 elements and another array also has 3 elements, then the resulting array will contain 6 elements.

A simple algorithm to merge two sorted arrays in a C program can be written as follows:

• You can start by creating two different sorted arrays with fixed sizes, and also define their items in a sorted manner.

• Now, consider two different variables such as m and n that will each be placed at 0th positions in both arrays.

• You can now start traversing both of the arrays using the m and n pointers in loop.

• These pointers will further help in navigating and storing the smaller elements, from both the arrays

• This process will continue until both of the arrays have been traversed entirely. Afterward, the remaining elements will automatically get sorted and selected after the smallest of the elements forming one single array.

Hence, using loops and pointers in a program makes it much easier to navigate through an entire array without having to search through particular elements.

There are multiple methods and approaches that can be applied for solving the problem of merging two sorted arrays using the C programming language.

Let's learn in-depth about solving this problem in the following section.

How to Merge Sorted Arrays in C

For merging two sorted arrays in a C program, consider the following problem statement. Afterward, we will have a look at the different approaches that can be applied for solving this problem.

Problem Statement

You have been given two sorted arrays. You are required to merge them in such a manner that they remain in a sorted order.

Input: arr1[] = {6, 7, 8, 9}

arr2[] = {1, 2, 3, 4}

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

Answer Key

You can use the brute force algorithm for a C program in order to solve this problem.

Method 1: Using the Naive Approach

The Naive Approach is also commonly referred to as the Brute Force Algorithm. This approach focuses on generating the solution as many times as possible using subproblems so that we can reach the required output effectively.

In this context, for merging two sorted arrays, we will be considering all the elements from the first and the second arrays and use simple algorithms to sort them into a third array.

Check out the implementation of this approach for the C program as follows:

• Start by traversing the first array, i.e., arr1, and start placing its elements in the third array i.e., arr3.

• Similarly, start a second traversal on arr2 and start inserting its elements in arr3.

• Now, simply run the sort function i.e., sort[] to sort the entire third array (arr3).

• This function will effectively merge the contents of both arrays, and you will have a third sorted array with elements from both the first and the second arrays.

Time Complexity for this approach:

O((m+n) log(m+n))

Method 2: Using (O(n1*n2) Time Complexity and 0(n1+n2) Space Complexity

This is a simple approach where we will be focusing on reducing the time and space complexities of the program.

You can follow the algorithms mentioned below for using this approach:

• Start by creating a third array i.e., arr3[] of the size n1+n2.

• Now, we can begin copying the elements from n1 of the first array i.e., arr1 into arr3.

• In a similar manner, traverse the entire second array, and start inserting elements from arr2 to arr3.

Time Complexity for this approach:

O(n1*n2)

Method 3: Using (O(n1+n2) Time Complexity and O(n1+n2) Space Complexity

This is a log time complexity that is often used for solving multiple programming problems such as finding the lca of bst.

Follow the steps mentioned below to implement this algorithm in a C program:

• Start by creating a third array i.e., arr3 of the size n1+n2.

• Now, begin traversing both the first and the second arrays i.e., arr1 and arr2.

• While performing the traversal, make sure to pick the smaller elements from both arrays, and copy them in a sorted position in the third.

• Perform the same action with the rest of the elements from both arrays.

• Finally, copy all the remaining elements from the first and the second arrays into arr3, and you will have a complete function to merge two sorted arrays.

Final Thoughts

Whenever we encounter the problem of merging sorted arrays, the sorting algorithm is always discussed first and foremost.

This is because the sort function facilitates sorting the entire data following an ascending order such as finding the lca of Binary Tree. The sort function essentially makes it easier to merge data within a program.