C Program to Merge Two Arrays Sorted in Descending Order

Combining two pre-sorted arrays into a single, descendingly ordered array presents a practical challenge in C programming. This guide delves into the steps and intricacies of achieving this efficiently, without resorting to an additional sorting algorithm.

1. Understanding the Task

We’re tasked with merging two arrays already sorted in descending order. The goal is to combine these elements into a new array, maintaining the descending order throughout. This requires an algorithm that intelligently combines and compares elements from both arrays without disrupting the pre-existing order.

2. Two-Pointer Approach

The most popular and efficient approach leverages two pointers, one for each array, and traverses them simultaneously. Here’s a breakdown of the steps:

1. Initialization:

• Declare three arrays: arr1 and arr2 for the original sorted arrays and mergedArray for the final result.
• Initialize two pointers, i for arr1 and j for arr2, starting at the rightmost element of each array (indicating the largest values).
• Set a counter, k, to track the insertion position in the mergedArray.

2. Comparison and Insertion:

• Inside a loop, compare the elements pointed to by i and j.
• If the element at i is greater than or equal to the element at j (remember, descending order), insert it into the mergedArray at position k and decrement i.
• Otherwise, if the element at j is greater, insert it into the mergedArray at position k and decrement j.
• Increment k in both cases to move to the next insertion position.

3. Handling Remaining Elements:

• After the loop finishes, one or both arrays might have leftover elements (due to potentially different sizes).
• If elements remain in arr1, directly copy them to the mergedArray, starting from the next available position indicated by k.
• Similarly, if elements remain in arr2, copy them to the mergedArray as well.

4. Printing the Merged Array:

• Iterate through the mergedArray from the beginning (index 0) to the final element (size – 1) and print its contents.

4. Code Implementation

Here’s the C code implementing the two-pointer approach:

C

#include <stdio.h>

void mergeArrays(int arr1[], int n1, int arr2[], int n2, int mergedArray[]) {
  int i = n1 - 1, j = n2 - 1, k = 0;

  while (i >= 0 && j >= 0) {
    if (arr1[i] >= arr2[j]) {
      mergedArray[k++] = arr1[i--];
    } else {
      mergedArray[k++] = arr2[j--];
    }
  }

  while (i >= 0) {
    mergedArray[k++] = arr1[i--];
  }

  while (j >= 0) {
    mergedArray[k++] = arr2[j--];
  }
}

int main() {
  int arr1[] = {7, 5, 3, 1};
  int arr2[] = {8, 6, 4, 2};
  int n1 = sizeof(arr1) / sizeof(arr1[0]);
  int n2 = sizeof(arr2) / sizeof(arr2[0]);
  int mergedArray[n1 + n2];

  mergeArrays(arr1, n1, arr2, n2, mergedArray);

  printf("Merged array in descending order: ");
  for (int i = 0; i < n1 + n2; i++) {
    printf("%d ", mergedArray[i]);
  }
  printf("\n");

  return 0;
}

This code demonstrates merging two arrays with sizes n1 and n2 into the mergedArray. Replace the sample arrays and sizes with your own data for testing.

Advantages and Considerations:

• Pre-sorted arrays: This approach relies on both arrays being pre-sorted in descending order. If your data needs sorting beforehand, additional steps or separate algorithms might be required.
• Handling equal elements: In case both arrays contain identical elements, the code as presented doesn’t specify their order in the merged array. You can modify the comparison logic or add specific handling for duplicates if needed.

Alternative Approaches

While the two-pointer approach is widely used, other methods can achieve merging sorted arrays. Here are two brief mentions:

• Merging with recursion: This involves recursively dividing the arrays into smaller halves, merging them in sorted order, and combining the results. It can be less intuitive but potentially efficient for very large datasets.
• Using library functions: Standard C libraries might offer functions like qsort that can handle merging already sorted arrays. This reduces code complexity but might be less customizable for specific needs.

Conclusion

Merging two sorted arrays in C requires efficient algorithms and careful consideration of the desired outcome. The two-pointer approach provides a well-balanced solution for most cases, while other methods offer different trade-offs in terms of complexity and functionality.

By understanding the different approaches and choosing the one that best suits your specific data and requirements, you can effectively combine pre-sorted arrays in your C programs.