C program to merge two sorted array

Write a C program to input elements in two array and merge two array to third array. How to merge two array in C programming. Logic to merge two sorted array to third array in C program.

Example

Input

Input first array elements: 1, 4, 6, 9, 15
Input second array elements: 2, 5, 8, 10

Output

Merged array in ascending order = 1, 2, 4, 5, 6, 8, 9, 10, 15

Required knowledge

Basic Input Output, If else, For loop, While loop, Array

Logic to merge two sorted array

Step by step descriptive logic to merge two sorted array.

  1. Input size and elements in two arrays and store them separately in two array variable. Say size1, arr1, size2 and arr2 stores size and elements of first and second array respectively.
  2. Create another array which will store the merge array with size mergeSize = size1 + size2, say mergeArray[mergeSize].
  3. Initialize two variable index1 = 0 and index2 = 0. Both these variables will keep track of total merged elements from given two array individually.
  4. Run a loop from 0 to mergeSize. The loop structure must look like for(mergeIndex=0; mergeIndex<mergeSize; mergeIndex++).
  5. Inside loop check for smallest element in two input array. Which is if(arr1[index1] < arr2[index2]) then assign element of first array to merge array i.e. mergeArray[mergeIndex] = arr1[index1] and increment index1. Otherwise store mergeArray[mergeIndex] = arr2[index2]; and increment index2.
  6. After loop merge the remaining array elements if any.

Program to merge two array in ascending order

/**
 * C program to merge two sorted array in ascending order
 */

#include <stdio.h>
#define MAX_SIZE 100      // Maximum size of the array

int main()
{
    int arr1[MAX_SIZE], arr2[MAX_SIZE], mergeArray[MAX_SIZE * 2];
    int size1, size2, mergeSize;
    int index1, index2, mergeIndex;
    int i;
     
    /* Input size of first array */
    printf("Enter the size of first array : ");
    scanf("%d", &size1);

    /* Input elements in first array */
    printf("Enter elements in first array : ");
    for(i=0; i<size1; i++)
    {
        scanf("%d", &arr1[i]);
    }

    /* Input size of second array */
    printf("\nEnter the size of second array : ");
    scanf("%d", &size2);

    /* Input elements in second array */
    printf("Enter elements in second array : ");
    for(i=0; i<size2; i++)
    {
        scanf("%d", &arr2[i]);
    }


    mergeSize = size1 + size2;


    /*
     * Merge two array in ascending order 
     */
    index1 = 0;
    index2 = 0;
    for(mergeIndex=0; mergeIndex < mergeSize; mergeIndex++)
    {
        /* 
         * If all elements of one array 
         * is merged to final array
         */
        if(index1 >= size1 || index2 >= size2)
        {
            break;
        }


        if(arr1[index1] < arr2[index2])
        {
            mergeArray[mergeIndex] = arr1[index1];
            index1++;
        }
        else
        {
            mergeArray[mergeIndex] = arr2[index2];
            index2++;
        }
    }

    /*
     * Merge remaining array elements
     */
    while(index1 < size1)
    {
        mergeArray[mergeIndex] = arr1[index1];
        mergeIndex++;
        index1++;
    }
    while(index2 < size2)
    {
        mergeArray[mergeIndex] = arr2[index2];
        mergeIndex++;
        index2++;
    }


    /* 
     * Print merged array
     */
    printf("\nArray merged in ascending order : ");
    for(i=0; i<mergeSize; i++)
    {
        printf("%d\t", mergeArray[i]);
    }

    return 0;
}

Important note: In order to merge array in ascending or descending order both array elements must be sorted in ascending or descending order.

Output

Enter the size of first array : 5
Enter elements in first array : 1 4 6 9 15

Enter the size of second array : 4
Enter elements in second array : 2 5 8 10

Array merged in ascending order : 1      2      4      5      6      8      9      10      15

Happy coding 😉