C Program to Merge Two Sorted Arrays

Problem: Write a C program to merge two sorted arrays into one sorted array.

Example:

Array I:   {1, 3, 6}
Array II:  {2, 5, 8}

Array III: {1, 2, 3, 5, 6, 8}

To solve this problem we have to merge the given two arrays in such a way that the resulting array would also be sorted.

To do so, we fill the third array by choosing the smaller element one by one from the given two sorted arrays.

Here is the C program that implements the same to merge the two sorted arrays into one:

#include <stdio.h>
#include <stdlib.h>

int main() {
    //sorted array I
    int arr1[] = {1, 4, 6, 8, 9};
    //sorted array II
    int arr2[] = {2, 3, 5, 7, 10};
    

    //declare an empty array (array III) of size n1+n2
    int size = sizeof(arr1)/sizeof(arr1[0]) + sizeof(arr2)/sizeof(arr2[0]);
    int arr3[size];
    
    //loop through the third array
    for(int i=0, j=0, k=0; k<size; ){
        /* If the element of the first array is small,
        add it to the third array otherwise, add the 
        element of the second array */
        if(arr1[i]< arr2[j])
            arr3[k++] = arr1[i++];
        else
            arr3[k++] = arr2[j++];
    }
    
    //output the third array
    printf("Array : ");
    for(int k=0; k<size; k++){
        printf("%d ", arr3[k]);
    }
    
    return 0;
}

Output: Array : 1 2 3 4 5 6 7 8 9 10

Explanation

In the above program, we have done the following:

1. Input the two sorted arrays
2. Find and add the size of the given arrays and declare a third array of the same size.
3. Loop through the index of the third array using for loop:
   1. Check which array has the smaller element and fill the third array with the same.
   2. If the first array has the smaller element (i.e. arr1[i] < arr2[j]) then fill the third array with the element of the first array (i.e. arr3[k++] = arr1[i++]) otherwise fill with the element of the second array (i.e. arr3[k++] = arr2[j++])
4. End loop
5. Output the third array.

In the program, we are initializing the third array with values and incrementing the indexes within the same expression.

The time and space complexity of the program is O(n1+n2), where n1 and n2 are the numbers of elements in the given two arrays respectively.

Conclusion

In this programming example, we learned to merge two sorted arrays into a single sorted array using the C language.