Merge two Sorted Arrays in C

Merging two arrays in c is similar to Concatenating or combining two arrays into a single array. For example, if the first array has four elements and the second array has five elements, the resulting array has nine elements.

Example:
First Array = [1, 2, 3, 4, 5]
Second Array = [6, 7, 8, 9, 10]

Merged Array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Problem Description

Write a C program to merge two sorted array elements into a single array.

Problem Solution

1. Create two arrays of some fixed size and define their elements in sorted fashion.
2. Take two variables i and j, which will be at the 0th position of these two arrays.
3. Elements will be compared one by one using i and j in for loop, and whichever element is smaller than the other, that element will get inserted to final array and the position(either i or j) will move by one, whereas the other array’s track position will remain in that same place.
4. Above work will be done till we reach the end of either array. After that, one of the array whose elements are still to be added, its elements will get straightaway added to the final array.

There are several ways to merge two sorted array elements into a single array in C language. Let’s take a detailed look at all the approaches to merge the elements of 2 sorted array.

Merge Two Sorted Arrays in C using For Loop
Merge Two Sorted Arrays in C using While Loop & 1D Array
Merge Two Sorted Arrays in C using Function
Merge Two Sorted Arrays in C using Pointers

Method 1: Merge Two Sorted Arrays in C using For Loop (Naive Approach)

In this approach, we will use a for loop to iterate through the array and merge the two arrays.

Example:
First Array = [12, 18, 23]
Second Array = [13, 19, 27]

Merged Array = [12, 13, 18, 19, 23, 27]

Program/Source Code

Note: Join free Sanfoundry classes at Telegram or Youtube

Here is source code of the C Program to merge two sorted arrays using for loop. The program is successfully compiled and tested using Turbo C compiler in windows environment. The program output is also shown below.

```
/*
```

 * C Program to merge two sorted arrays using for loop

```
 */
```
```
 
```
```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
int main(void)
```
```
{
```
```
    int i, n, j, k;
```

    printf("Enter the size of the first array: ");

```
    scanf("%d", &n);
```
```
    int arr1[n];
```

    printf("Enter the elements of the first array: \n");

```
    for (i = 0; i < n; i++)
```
```
    {
```
```
        scanf("%d", &arr1[i]);
```
```
    }
```

    printf("Enter the size of the second array: ");

```
    scanf("%d", &k);
```
```
    int arr2[k];
```

    printf("Enter the elements of the second array: \n");

```
    for (j = 0; j < k; j++)
```
```
    {
```
```
        scanf("%d", &arr2[j]);
```
```
    }
```
```
    int arr3[n + k];
```
```
    i = j = 0;
```
```
    int in;
```
```
    for (in = 0; in < n + k; in ++)
```
```
    {
```
```
        if (i < n && j < k)
```
```
        {
```
```
            if (arr1[i] < arr2[j])
```
```
            {
```
```
                arr3[in] = arr1[i];
```
```
                i++;
```
```
            }
```
```
            else
```
```
            {
```
```
                arr3[in] = arr2[j];
```
```
                j++;
```
```
            }
```
```
        }
```
```
        else if (i < n)
```
```
        {
```
```
            arr3[in] = arr1[i];
```
```
            i++;
```
```
        }
```
```
        else
```
```
        {
```
```
            arr3[in] = arr2[j];
```
```
            j++;
```
```
        }
```
```
    }
```
```
    printf("The merged array is: \n");
```
```
    for (in = 0; in < n + k; in++)
```
```
    {
```
```
        printf("%d ", arr3[in]);
```
```
    }
```
```
    printf("\n");
```
```
    return 0;
```
```
}
```

Program Explanation

1. The program starts with the declaration of two arrays of integers.
2. The first and the second array are initialized with the size of the array.
3. The elements of the first and the second array are then entered by the user.
4. A loop is used to iterate through the array and merge the two arrays.
5. Print the merged array.

Time Complexity: O(n + k)
The time complexity of this algorithm is O(n + k), where n is the size of the first array and k is the size of the second array. This simplifies to O(n) as the loop is executed only once.

Space Complexity: O(n + k)
The space complexity of this algorithm is O(n + k), where n is the size of the first array and k is the size of the second array.

Runtime Test Cases

The runtime output of the C program is shown below, where the size of the first array is “3” and the items are 12, 18, and 23. The second array’s size is “3” and the items are 13, 19, and 27. It then combines both array elements and displays it.

Enter the size of the first array: 3
Enter the elements of the first array: 
12
18
23
Enter the size of the second array: 3
Enter the elements of the second array: 
13
19
27
The merged array is: 
12 13 18 19 23 27

Method 2: Merge Two Sorted Arrays in C using While Loop

In this approach, we will use a while loop to iterate through the array and merge the two arrays.

Example:
First Array = [12, 18, 40, 60]
Second Array = [47, 56, 89, 90]

Merged Array = [12, 18, 40, 47, 56, 60, 89, 90]

Program/Source Code

Here is source code of the C Program to merge two sorted arrays using while loop. The program is successfully compiled and tested using Turbo C compiler in windows environment. The program output is also shown below.

```
/*
```

 * C Program to merge two sorted arrays using while loop

```
 */
```
```
 
```
```
#include <stdio.h>
```
```
void main()
```
```
{
```

    int array1[50], array2[50], array3[100], m, n, i, j, k = 0;

    printf("\n Enter size of array Array 1: ");

```
    scanf("%d", &m);
```
```
 
```

    printf("\n Enter sorted elements of array 1: \n");

```
    for (i = 0; i < m; i++) 
```
```
    {
```
```
        scanf("%d", &array1[i]);
```
```
    }
```
```
 
```

    printf("\n Enter size of array 2: ");

```
    scanf("%d", &n);
```
```
 
```

    printf("\n Enter sorted elements of array 2: \n");

```
    for (i = 0; i < n; i++) 
```
```
    {
```
```
        scanf("%d", &array2[i]);
```
```
    }
```
```
 
```
```
    i = 0;
```
```
    j = 0;
```
```
 
```
```
    while (i < m && j < n) 
```
```
    {
```
```
        if (array1[i] < array2[j]) 
```
```
        {
```
```
            array3[k] = array1[i];
```
```
            i++;
```
```
        }
```
```
        else 
```
```
        {
```
```
            array3[k] = array2[j];
```
```
            j++;
```
```
        }
```
```
        k++;
```
```
    }
```
```
 
```
```
    if (i >= m) 
```
```
    {
```
```
        while (j < n) 
```
```
        {
```
```
            array3[k] = array2[j];
```
```
            j++;
```
```
            k++;
```
```
        }
```
```
    }
```
```
 
```
```
    if (j >= n) 
```
```
    {
```
```
        while (i < m)
```
```
        {
```
```
            array3[k] = array1[i];
```
```
            i++;
```
```
            k++;
```
```
        }
```
```
    }
```
```
 
```
```
    printf("\n After merging: \n");
```
```
    for (i = 0; i < m + n; i++) 
```
```
    {
```
```
        printf("\n%d", array3[i]);
```
```
    }
```
```
}
```

Program Explanation

1. Declare 2 1D arrays of some fixed size, then take size of the arrays from user and define all the elements of the array according to the size in sorted fashion.
2. Take two variables, i and j as iterators which will track the position of elements in arrays.
3. Running a while loop till we reach the end of either array, the element at ith and jth position of two arrays are compared.
4. The smaller element gets inserted into final array (third array, whose size is the sum of the size of these two arrays) and the track position gets incremented by 1.
5. This process continues, till we reach the end of either array.
6. After finishing the loop above, one of the array’s tracker(i.e either i or j) will not be at the last position of the corresponding array, in that case we will have to add all the remaining elements of that array to the final array as it is one by one.

Space Complexity: O(n + k)
The space complexity of this algorithm is O(n + k), where n is the size of the first array and k is the size of the second array.

Runtime Test Cases

The runtime output of the C program to merge two sorted arrays is shown below, where the size of the first array is “4” and the elements are 12, 18, 40, and 60. The second array’s size is “4” and the elements are 47, 56, 89 and 90. It then combines both array elements and displays it.

Enter size of array Array 1: 4
Enter sorted elements of array 1:
12
18
40
60
Enter size of array 2: 4
 
Enter sorted elements of array 2:
47
56
89
90
After merging:
12
18
40
47
56
60
89
90

Method 3: Merge Two Sorted Arrays in C using Function

In this approach, we will use functions to merge the two arrays.

Example:
First Array = [12, 56, 99]
Second Array = [15, 60]

Merged Array = [12, 15, 56, 60, 99]

Program/Source Code

Here is source code of the C Program to merge two sorted arrays using function. The program is successfully compiled and tested using Turbo C compiler in windows environment. The program output is also shown below.

```
/*
```

 * C Program to merge two sorted arrays using function

```
 */
```
```
 
```
```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
void init(int *arr, int n)
```
```
{
```
```
    int i;
```
```
    for (i = 0; i < n; i++)
```
```
    {
```
```
        printf("%d ", i);
```
```
        scanf("%d", &arr[i]);
```
```
    }
```
```
}
```
```
 
```
```
void print_array(int *arr, int n)
```
```
{
```
```
    int i;
```
```
    printf("[ ");
```
```
    for (i = 0; i < n; i++)
```
```
    {
```
```
        printf("%d ", arr[i]);
```
```
    }
```
```
    printf("]\n");
```
```
}
```
```
 
```

void merge(int *arr1, int *arr2, int *arr3, int n, int k)

```
{
```
```
    int i = 0, j = 0, in = 0;
```
```
    while (i < n && j < k)
```
```
    {
```
```
        if (arr1[i] < arr2[j])
```
```
        {
```
```
            arr3[in] = arr1[i];
```
```
            i++;
```
```
        }
```
```
        else
```
```
        {
```
```
            arr3[in] = arr2[j];
```
```
            j++;
```
```
        }
```
```
        in++;
```
```
    }
```
```
    while (i < n)
```
```
    {
```
```
        arr3[in] = arr1[i];
```
```
        i++;
```
```
        in++;
```
```
    }
```
```
    while (j < k)
```
```
    {
```
```
        arr3[in] = arr2[j];
```
```
        j++;
```
```
        in++;
```
```
    }
```
```
}
```
```
 
```
```
int main(void)
```
```
{
```
```
    int i, n, j, k;
```

    printf("Enter the size of the first array: ");

```
    scanf("%d", &n);
```
```
    int arr1[n];
```

    printf("Enter the elements of the first array: \n");

```
    init(arr1, n);
```

    printf("Enter the size of the second array: ");

```
    scanf("%d", &k);
```
```
    int arr2[k];
```

    printf("Enter the elements of the second array: \n");

```
    init(arr2, k);
```
```
    int arr3[n + k];
```
```
    merge(arr1, arr2, arr3, n, k);
```
```
    printf("The merged array is: \n");
```
```
    print_array(arr3, n + k);
```
```
    return 0;
```
```
}
```

Program Explanation

1. The program asks the user to enter the size of the first and the second array.
2. The elements of the first and the second array are then entered by the user.
3. The arrays are then merged using the merge_arrays function.
4. memcpy to append the first array to the second array.
5. Use separate functions for printing array, merging the arrays and initializing the arrays.
6. The merged array is then printed.
7. The memory is allocated using malloc.

Space Complexity: O(n + k)
The space complexity of this algorithm is O(n + k), where n is the size of the first array and k is the size of the second array.

Time Complexity: O(N)
The time complexity of this algorithm is O(N), where n is the size of the arrays.

Runtime Test Cases

The runtime output of the C program to merge two sorted arrays is shown below, where the size of the first array is “3” and the elements are 12, 56, and 99. The second array’s size is “2” and the elements are 15 and 60. It then combines both array elements and displays it.

Enter the size of the first array: 3
Enter the elements of the first array: 
12
56
99
Enter the size of the second array: 2
Enter the elements of the second array: 
15
60
The merged array is: 
[ 12 15 56 60 99 ]

Method 4: Merge Two Sorted Arrays in C using Pointers

In this approach, we will use pointers to merge the two arrays.

Program/Source Code

Here is source code of the C Program to merge two sorted arrays using pointers. The program is successfully compiled and tested using Turbo C compiler in windows environment. The program output is also shown below.

```
/*
```

 * C Program to merge two sorted arrays using pointers

```
 */
```
```
 
```
```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
int main(void)
```
```
{
```
```
    int i, n, j, k;
```

    printf("Enter the size of the first array: ");

```
    scanf("%d", &n);
```
```
    int arr1[n];
```

    printf("Enter the elements of the first array: \n");

```
    for (i = 0; i < n; i++)
```
```
    {
```
```
        scanf("%d", &arr1[i]);
```
```
    }
```

    printf("Enter the size of the second array: ");

```
    scanf("%d", &k);
```
```
    int arr2[k];
```

    printf("Enter the elements of the second array: \n");

```
    for (j = 0; j < k; j++)
```
```
    {
```
```
        scanf("%d", &arr2[j]);
```
```
    }
```

    int *arr3 = (int *)malloc((n + k) * sizeof(int));

```
    i = j = 0;
```
```
    int in;
```
```
    for (in = 0; in < n + k; in ++)
```
```
    {
```
```
        if (i < n && j < k)
```
```
        {
```
```
            if (arr1[i] < arr2[j])
```
```
            {
```
```
                arr3[in] = arr1[i];
```
```
                i++;
```
```
            }
```
```
            else
```
```
            {
```
```
                arr3[in] = arr2[j];
```
```
                j++;
```
```
            }
```
```
        }
```
```
        else if (i < n)
```
```
        {
```
```
            arr3[in] = arr1[i];
```
```
            i++;
```
```
        }
```
```
        else
```
```
        {
```
```
            arr3[in] = arr2[j];
```
```
            j++;
```
```
        }
```
```
    }
```
```
    printf("The merged array is: \n");
```
```
    for (in = 0; in < n + k; in++)
```
```
    {
```
```
        printf("%d ", arr3[in]);
```
```
    }
```
```
    printf("\n");
```
```
    return 0;
```
```
}
```

Program Explanation

1. The program asks the user to enter the size of the first and the second array.
2. The elements of the first and the second array are then entered by the user.
3. A loop is then used to iterate through the array and merge the two arrays.
4. The merged array is then printed.

Space Complexity: O(n + k)
The space complexity of this algorithm is O(n + k), where n is the size of the first array and k is the size of the second array.

Time Complexity: O(N)
The time complexity of this algorithm is O(N), where n is the size of the arrays.

Runtime Test Cases

The runtime output of the C program to merge two sorted arrays is shown below, where the size of the first array is “4” and the elements are 5, 9, 15 and 33. The second array’s size is “5” and the elements are 1, 14, 24, 29, and 37. It then combines both array elements and displays it.

Enter the size of the first array: 4
Enter the elements of the first array: 
5
9
15
33
Enter the size of the second array: 5
Enter the elements of the second array: 
1
14
24
29
37
The merged array is: 
1 5 9 14 15 24 29 33 37

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Implement Merge Sort Algorithm

» Next - C Program to Implement Selection Sort using Recursion

Related Posts:

Recommended Articles: