Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach1
2.1.
Algorithm
2.2.
Implementation 
2.3.
Output
2.4.
Complexity Analysis 
3.
Approach2
3.1.
Algorithm
3.2.
Implementation
3.3.
Output
3.4.
Complexity Analysis 
4.
Frequently asked questions
4.1.
What is an array?
4.2.
How can we access an element in an array?
4.3.
What is recursion?
5.
Conclusion
Last Updated: Mar 27, 2024

C program to merge two sorted array in descending order

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

We are going to know how we can merge the two sorted arrays given to us and sort the merged array but in descending order. Let's assume we have array1 with n number of elements and array 2 with m number of elements in it. Our desired output is to have an array 3 with n+m number of elements of both of the given array, and this array three should be sorted in descending order with efficient time complexity.

 

 

Also Read, Binary to Hex Converter and C Static Function.

Approach1

We are going to learn two approaches to how we can handle this problem. In this first approach, we will sort the array in descending order by selecting one element at a time and will iterate over the rest of the elements and start comparing with them until we find an element greater than that and swap the positions of those elements. We will loop over this logic until the array is sorted.

Algorithm

  1. Declare the size of arrays.
  2. Take input of size of arrays.
  3. Initialize array1 and array2.
  4. Copy the elements of the first array to the merged array when initializing it.
  5. Copy the elements of the second array to the merged array while initializing the second array.
  6. Sort the merged array.
  7. Display the array result.
     

Implementation 

#include <stdio.h>
int main() {
  /*Array Size Declaration*/
  int size1, size2, size3;
  printf("\nEnter the size for the first array: ");
  scanf("%d", & size1);
  printf("\nEnter the size for the second array: ");
  scanf("%d", & size2);
  
  size3 = size1 + size2;
  printf("\nEnter the elements in a sorted manner:");
  
  /*Array Declaration*/
  int array1[size1], array2[size2], array3[size3];
  /*Array Initialized*/
  for (int i = 0; i < size1; i++) {
    scanf("%d", & array1[i]);
    array3[i] = array1[i];
  }
  int k = size1;
  printf("\nEnter the elements in a sorted manner:");
  /*Array Initialized*/
  for (int i = 0; i < size2; i++) {
    scanf("%d", & array2[i]);
    array3[k] = array2[i];
    k++;
  }
  printf("\nmerged array of first and second:\n");
  for (int i = 0; i < size3; i++)
    /*Printing the merged array*/
    printf("%d ", array3[i]);

  printf("\nsorted array in descending order\n");
  /*Sorting Array*/
  for (int i = 0; i < size3; i++) {
    int temp;
    for (int j = i + 1; j < size3; j++) {
      if (array3[i] < array3[j]) {
        temp = array3[i];
        array3[i] = array3[j];
        array3[j] = temp;
      }
    }
  }
  /*Printing the sorted Array*/
  for (int i = 0; i < size3; i++) {
    printf(" %d ", array3[i]);
  }
  return 0;
}

Output

Complexity Analysis 

Time complexity: O((n+m)2), where n and m are the sizes of the first and second array respectively. 

Space complexity: O(n+m)

Also Read - Selection Sort in C

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach2

This approach might be a little complicated if you are new to the programming because  recursion logic is used in this approach. In this method we have used merge sort with recursion to sort the array. 

Merge sort is a divide and conquer algorithm which divides the array into subarrays until we have only 1 element in subarrays and recursively merge and sort the subarrays into a complete sorted array.

This approach sorts the array in O(nlogn) complexity thats why this approach is good in solving the array when we have large data,

Algorithm

  1. Declare the size of arrays.
  2. Take input of size of arrays.
  3. Declare the arrays.
  4. Initialize array1 and array2.
  5. Copy the elements of the first array to the merged array when initializing it.
  6. Copy the elements of the second array to the merged array while initializing the second array.
  7. Call the mergesort function to divide the array into subarrays by finding the middle element using m = l +(r-l)/2 where l = index of first element of array and r = index of last element of array.
  8. After dividing the array into subarray, recursively merge and sort the array into descending order using merge function.
  9. Print the sorted array on the screen

Implementation

#include<stdlib.h>
#include<stdio.h>
 // Merge Function
void merge(int arr[], int l, int m, int r) {
  int i, j, k;
  int n1 = m - l + 1;
  int n2 = r - m;
  int L[n1], R[n2];
  for (i = 0; i < n1; i++)
    L[i] = arr[l + i];
  for (j = 0; j < n2; j++)
    R[j] = arr[m + 1 + j];
  i = 0;
  j = 0;
  k = l;
  while (i < n1 && j < n2) {
    if (L[i] >= R[j]) {
      arr[k] = L[i];
      i++;
    } else {
      arr[k] = R[j];
      j++;
    }
    k++;
  }
  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }
  while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
  }
}


void mergeSort(int arr[], int l, int r) {
  if (l < r) {
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
  }
}


void printArray(int A[], int size) {
  int i;
  for (i = 0; i < size; i++)
    printf("%d ", A[i]);
}


int main() {
  /*Array Size Declaration*/
  int size1, size2, size3;
  printf("\nEnter the size for the first array: ");
  scanf("%d", & size1);
  printf("\nEnter the size for the second array: ");
  scanf("%d", & size2);


  size3 = size1 + size2;
  printf("\nEnter the elements in a sorted manner:");
  /*Array Declaration*/
  int array1[size1], array2[size2], array3[size3];
  /*Array Initialized*/
  for (int i = 0; i < size1; i++) {
    scanf("%d", & array1[i]);
    array3[i] = array1[i];
  }
  int k = size1;
  printf("\nEnter the elements in a sorted manner:");
  /*Array Initialized*/
  for (int i = 0; i < size2; i++) {
    scanf("%d", & array2[i]);
    array3[k] = array2[i];
    k++;
  }
  printf("Given array is \n");
  printArray(array3, size3);
  mergeSort(array3, 0, size3 - 1);
  printf("\nSorted array is \n");
  printArray(array3, size3);
  return 0;
}

Output

Complexity Analysis 

Time complexity: O(nlogn) here n is the size of the merged array that is array3

Space complexity: O(n)

You can also read about dynamic array in c and  Tribonacci Series.

Must Read what is storage class in c

Frequently asked questions

What is an array?

An array is a container that contains collections of elements having the same datatype like int , float,char and double. It stores the elements in a continuous manner.

How can we access an element in an array?

Each element in an array has an unique index through which we can access them and perform some operations.

What is recursion?

Recursion is the process of calling a function by itself, and a recursive function is a function that calls itself. Recursion is a technique for solving various mathematical problems by breaking them down into smaller chunks.

Conclusion

In this article, we learned about how we can merge two sorted arrays and sort the merged array into descending order.

Recommended Problem - Merge K Sorted Arrays

To learn more about c programming, please refer to the following articles.

Recommended Readings:

To learn more about DSA, competitive coding and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Please upvote our blog to help other ninjas grow.

Happy Learning

Previous article
C Program to arrange the string in alphabetical order
Next article
C program to merge two sorted array in ascending order
Live masterclass