C program to merge two sorted array in ascending order

Introduction

In this blog we will discuss the approach to merge two sorted array in ascending order. Before jumping on to the approach to the problem, let us first understand the problem.

Also see: C Static Function and Short int in C Programming

Problem Statement

The primary goal is to merge two sorted arrays in ascending order and display the results as output.

Combining two arrays into a single array is known as merging two arrays. For example, if the first array has 5 elements and the second array has 4, the resultant array will have 9 elements. A merged array is the result of this process.

 If you are unfamiliar with the concept of an array, let's see the example :

Array in Javascript

Approach 1:🧑‍🎓

Let's look at step-by-step descriptive logic to merge two sorted arrays in ascending order.

Algorithm 

1. Start the program

2. Input the length of both the arrays. 

3. Input the arrays elements from user. 

4. Copy the elements of the first array to the merged array when initialising it. 

5. Copy the elements of the second array to the merged array while initialising the second array.

6. Sort the merged array now.

7. Display the merged array.

8. The program ends here.

Implementation 

#include <stdio.h>


int main() {
  //Declaring the size of arrays
  int s1, s2, s3;
  printf("\n Enter the size of 1st array  ");
  scanf("%d", & s1);
  printf("\n Enter the size of 2nd array ");
  scanf("%d", & s2);


  s3 = s1 + s2;
  printf("\n Enter the elements of 1st array\n");
  // Declaring the array
  int arr1[s1], arr2[s2], arr3[s3];
  //Initialising the array 
  for (int i = 0; i < s1; i++) {
    scanf("%d", & arr1[i]);
    arr3[i] = arr1[i];
  }
  int k = s1;
  printf("\nEnter the elements of 2nd array \n");
  for (int i = 0; i < s2; i++) //Array Initialised
  {
    scanf("%d", & arr2[i]);
    arr3[k] = arr3[i];
    k++;
  }
  printf("\nThe merged array before sorting : \n\t");
  for (int i = 0; i < s3; i++)
    printf("%d ", arr3[i]); //Print the merged array before sorting


  printf("\n The merged array after sorting\n\t");
  for (int i = 0; i < s3; i++) //Sorting the array
  {
    int tem;
    for (int j = i + 1; j < s3; j++) {
      if (arr3[i] > arr3[j]) {
        tem = arr3[i];
        arr3[i] = arr3[j];
        arr3[j] = tem;
      }
    }
  }

  for (int i = 0; i < s3; i++) //Printing the sorted Array 
  {
    printf(" %d ", arr3[i]);
  }
}

Output : 

Time complexity: (n+m)^2  since we are applying insertion sort on the merged array. 

Auxiliary Space: O(n+m)

You can also read about dynamic array in c.

Approach 2:🧑‍🎓

Now for the second approach to merge two sorted arrays in ascending order,  we need to fill the third array by comparing and inserting the smaller element one by one from the given sorted arrays. Let's look at step-by-step descriptive logic 

for this approach.

Algorithm 

1. Enter the two sorted arrays.

2. Find the size of the provided arrays and put them together, then declare a third     array of the same size.

3. If the first array has the smaller element (i.e. array1[i] < array2[j]), fill the third array with the first array's element (i.e. array3[k++] = array1[i++]), otherwise with the second array's element (i.e. array3[k++] = array2[j++]).

4. Print the output which will be the third array .

Implementation

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

int main() {
  // array1
  int array1[] = {1,4,6,8,9};
  //array2
  int array2[] = {2,3,5,7,10};


  //declaring an empty array3 of size array1+array2
  int len = sizeof(array1) / sizeof(array1[0]) + sizeof(array2) / sizeof(array2[0]);
  int array3[len];


  //loop for the third array
  for (int i = 0, j = 0, k = 0; k < len;) {
    /* If the first array's element is small, add this to the third array; otherwise, add the second array's element. */
    if (array1[i] < array2[j])
      array3[k++] = array1[i++];
    else
      array3[k++] = array2[j++];
  }


  //printing the output of the third array
  printf("The sorted Array in ascending order : ");
  for (int k = 0; k < len; k++) {
    printf("%d ", array3[k]);
  }


  return 0;
}

Output 

Within the same expression, we are initialising the third array with values and incrementing the indexes.

The program has an O(n1+n2) time and space complexity, where n1 and n2 are the number of elements in the two arrays, respectively.

Refer to know about :  Topological sort

Frequently Asked Questions

To merge two sorted lists, how many comparisons would be required in the worst case for merge sort?

In the worst case, m+n-1 comparisons are required to merge two lists of size m and n.

What is the most best case for merging the two sorted arrays into one sorted array?

O(m + n), where 'm' is the array's size of  'arr1', and 'n' is the array's size of  'arr2'. It takes O(m + n) time to merge the elements of 'arr1' and 'arr2' in 'arr3.'

In C, why do we return 0?

C language return's value of 0 in the main function indicates that the program ran successfully. The return 1 in the main function shows that the program did not run correctly and that an error occurred.

In the C programming language, which loop is the fastest?

In C programming, the Do-While loop is the fastest loop.