C Program To Merge Two Sorted Arrays

Merging two arrays means combining two separate arrays into one single array. For instance, if the first array consists of 3 elements and the second array consists of 5 elements then the resulting array consists of 8 elements. This resulting array is known as a merged array. Before moving forward, if you are not familiar with the concept of the array then, do check the article on Arrays in C.

We are given two sorted arrays and our task is to merge these two sorted arrays.

Input: First Array: 5 4 3 2 1

Second Array: 9 8 7 6 5

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

Method 1: Merge and then Sort

In this method, we will enter two sorted arrays as input and then merge them. After merging them, we will sort the merged array and display the output.

Algorithm

• Input the two sorted array sizes and their elements.
• Declare another array with size equal to the sum of both sorted arrays.
• Copy the elements of first array into final array.
• Copy the elements of second array into the final array.
• Sort the final array.
• Print the results.

In the below program firstly we declare and input two arrays. Now, merge these arrays and then sort the array.

#include <stdio.h>
int main()
{
    int n1,n2,n3;            //Array Size Declaration
    int a[10000], b[10000], c[20000];
    printf("Enter the size of first array: ");
    scanf("%d",&n1);
    printf("Enter the array elements: ");
    for(int i = 0; i < n1; i++)      
       scanf("%d", &a[i]);
    printf("Enter the size of second array: ");
        scanf("%d",&n2);
    printf("Enter the array elements: ");
    for(int i = 0; i < n2; i++)      
       scanf("%d", &b[i]);
    n3 = n1 + n2;
    for(int i = 0; i < n1; i++)
       c[i] = a[i];
    for(int i = 0; i < n2; i++)     
        c[i + n1] = b[i];
        
    printf("The merged array: ");
    for(int i = 0; i < n3; i++)
        printf("%d ", c[i]);        //Print the merged array
    
    printf("\nFinal array after sorting: ");
    for(int i = 0; i < n3; i++){
        int temp;
        for(int j = i + 1; j < n3; j++) {
            if(c[i] > c[j]) {
                temp = c[i];
                c[i] = c[j];
                c[j] = temp;
            }
        }
    }   
    for(int i = 0; i < n3 ; i++)       //Print the sorted Array 
        printf(" %d ",c[i]);
    return 0;   
}

Enter the size of first array: 5
Enter the array elements: 1 23 43 54 87
Enter the size of second array: 3
Enter the array elements: -45 0 4
The merged array: 1 23 43 54 87 -45 0 4
Final array after sorting: -45 0 1 4 23 43 54 87

We can also pass the final array to a function which will sort and return the final merged array.

Method 2: Merge and Sort simultaneously

In this method, we will enter two sorted arrays. While merging them, we will compare the elements of both the arrays and merge them in a sorted manner.

Algorithm

• Input the two sorted arrays, say a and b, which are to be merged.
• Create another array, say c with size equal to the sum of the two sorted arrays.
• Traverse the two stored arrays simultaneously.
• While traversing, select the smaller of current elements of a and b and copy it at the next position in c.
• Increment the iterator of c and the array whose element has been picked.
• If there are any remaining elements in a or b, copy them in c.

#include <stdio.h>
int main()
{
    int n1,n2,n3;            //Array Size Declaration
    int a[10000], b[10000], c[20000];
    printf("Enter the size of first array: ");
    scanf("%d",&n1);
    printf("Enter the array elements: ");
    for(int i = 0; i < n1; i++)      
       scanf("%d", &a[i]);
    printf("Enter the size of second array: ");
    scanf("%d",&n2);
    printf("Enter the array elements: ");
    for(int i = 0; i < n2; i++)      
       scanf("%d", &b[i]);
    n3 = n1 + n2;
    int i = 0, j = 0, k = 0;

    while (i < n1 && j < n2)    //this loop will run till a or b is completely traversed
    {
        if (a[i] < b[j])
            c[k++] = a[i++];    //here, as soon as we copy an element in c, we increment the iterator so that the next element is copied at next index. 
//When we copy an element from a to c, we increment i also because now we will compare with the next element of a.
        else
            c[k++] = b[j++];
    }
  
    while (i < n1)    //copying the leftover elements of a, if any
        c[k++] = a[i++];
  
    while (j < n2)    //copying the leftover elements of b, if any
        c[k++] = b[j++];
    
    printf("Final array after merging: ");
    for(int i = 0; i < n3 ; i++)       //Print the sorted Array 
        printf(" %d ",c[i]);
    return 0;   
}

Enter the size of first array: 4
Enter the array elements: -2 0 45 86
Enter the size of second array: 6
Enter the array elements: -7 -5 56 78 109 112
Final array after merging: -7 -5 -2 0 45 56 78 86 109 112