Home » Data Structure

Program to merge two sorted arrays into a third sorted array in data structure

In this article, we will look up on what is sorting and merge two sorted array into third sorted array. Here, is a C program that will arrays and result will also be a sorted array. By Manu Jemini, on January 18, 2018

Merge two sorted arrays into a third sorted array

When we say sorting it means serializing a collection of data inside any the collections like arrays, linked list etc. There is one good reason for implementing sorting on any collection is that it makes the searching very fast as compared to the collection which is unsorted. Now, this is not true for every test case but on an average, it is so.

The Above example shows how a merge sort works. Let us assume that we have an array of integers and from the middle index we split it and again split it, till every sub-array is sorted and then merge them in one by one and keep sorting them when the sub-arrays merge into a big sub-array.

In the example below, we provide it in a different way. We take two arrays:

A => 534, 7, 3333    
B => 353, 543, 6, 2

The Following program sorts the array A in the same way we saw above and then, do it for array B. So it will like:

    A => 7, 534, 3333
    B => 2, 6, 353, 543

Now we got two sorted arrays, the time to join them together has come. This will be done by combining A and B. So we create C whose size is equal to A and B.

    C => 7, 534, 3333, 2, 6, 353, 543

With a little cost, we will sort it and have a combination of two sorted arrays.

C program to merge two sorted array

#include<stdio.h>

#define MAX 20

void bubble_sort(int arr[], int size) {
  int i, j, temp;
  for (i = 0; i < size; i++) {
    for (j = 0; j < size - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;

      } /*End of if*/
    } /*End of inner for loop*/
  } //end of outer loop

}

void merge(int arr1[], int size1, int arr2[], int size2, int arr3[]) {
  /* Merging */
  int i = 0; /*Index for first array*/
  int j = 0; /*Index for second array*/
  int k = 0; /*Index for merged array*/

  while ((i < size1) && (j < size2)) {
    if (arr1[i] < arr2[j])
      arr3[k++] = arr1[i++];
    else
      arr3[k++] = arr2[j++];
  } /*End of while*/
  /*Put remaining elements of arr1 into arr3*/
  while (i < size1)
    arr3[k++] = arr1[i++];
  /*Put remaining elements of arr2 into arr3*/
  while (j < size2)
    arr3[k++] = arr2[j++];

  /*Merging completed*/

}

int main() {
  int arr1[MAX], arr2[MAX], arr3[40];
  int i, j, k;
  int size1, size2;

  printf("Enter the number of elements in list1 : ");
  scanf("%d", & size1);
  printf("Take the elements  :\n");
  for (i = 0; i < size1; i++) {
    printf("Enter element %d : ", i + 1);
    scanf("%d", & arr1[i]);
  }
  bubble_sort(arr1, size1);

  printf("Enter the number of elements in list2 : ");
  scanf("%d", & size2);
  printf("Take the elements  :\n");
  for (i = 0; i < size2; i++) {
    printf("Enter element %d : ", i + 1);
    scanf("%d", & arr2[i]);
  }

  bubble_sort(arr2, size2);

  merge(arr1, size1, arr2, size2, arr3);
  printf("\nMerged list : ");
  for (i = 0; i < size1 + size2; i++)
    printf("%d ", arr3[i]);
  printf("\n");
  
  return 0;
} /*End of main()*/

Output