Merge Two Sorted Arrays in C Program

In this article, you will learn how to efficiently combine two arrays that are already sorted into a single, new sorted array using the C programming language.

Problem Statement

Merging two sorted arrays is a fundamental operation in computer science, often encountered in algorithms like Merge Sort. The challenge is to combine two arrays, each containing elements in ascending order, into a single array that also maintains its elements in ascending order, ideally with optimal time complexity.

Example

Let's say we have two sorted arrays: arr1 = [1, 3, 5, 7] arr2 = [2, 4, 6, 8]

The desired output after merging should be: merged_arr = [1, 2, 3, 4, 5, 6, 7, 8]

Background & Knowledge Prerequisites

To understand this article, you should have a basic understanding of:

• C Programming Basics: Variables, loops (for, while), functions.
• Arrays: Declaring, initializing, and accessing elements.
• Pointers (optional but helpful): For understanding array traversal.
• Sorting Concepts: What it means for an array to be sorted.

 

Use Cases or Case Studies

Merging sorted arrays is crucial in various scenarios:

1. Merge Sort Algorithm: This divide-and-conquer sorting algorithm recursively divides an array into halves, sorts them, and then merges the sorted halves back together.
2. Database Management Systems: When combining results from two sorted queries or indices, merging is often used to produce a unified, sorted result set efficiently.
3. Data Stream Processing: Combining two sorted streams of data (e.g., time-series data from two different sensors) into a single, ordered stream.
4. File System Utilities: Tools that merge sorted log files or lists of items often employ this logic.

 

Solution Approaches

We will explore two common approaches to merge two sorted arrays:

1. The Two-Pointer Approach (Optimal): This method efficiently combines the arrays by comparing elements from both arrays simultaneously.
2. Naive Approach (Concatenate and Sort): This simpler but less efficient method combines arrays first, then sorts the combined result.

 

Approach 1: The Two-Pointer Approach with Auxiliary Array

This is the most efficient and widely used method. It leverages the fact that both input arrays are already sorted. We use three pointers: two for iterating through the input arrays and one for placing elements into the merged array.

• One-line summary: Iterate through both arrays simultaneously, comparing elements and placing the smaller one into a new result array until all elements are merged.

 

// Merge Two Sorted Arrays (Two-Pointer Approach)
#include <stdio.h>
#include <stdlib.h> // Required for malloc

void mergeSortedArrays(int arr1[], int n1, int arr2[], int n2, int mergedArr[]) {
    int i = 0; // Pointer for arr1
    int j = 0; // Pointer for arr2
    int k = 0; // Pointer for mergedArr

    // Step 1: Compare elements from both arrays and place the smaller one
    while (i < n1 && j < n2) {
        if (arr1[i] <= arr2[j]) {
            mergedArr[k++] = arr1[i++];
        } else {
            mergedArr[k++] = arr2[j++];
        }
    }

    // Step 2: Add remaining elements from arr1 (if any)
    while (i < n1) {
        mergedArr[k++] = arr1[i++];
    }

    // Step 3: Add remaining elements from arr2 (if any)
    while (j < n2) {
        mergedArr[k++] = arr2[j++];
    }
}

int main() {
    int arr1[] = {1, 3, 5, 7};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);

    int arr2[] = {2, 4, 6, 8, 9};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);

    int n_merged = n1 + n2;
    int *mergedArr = (int *)malloc(n_merged * sizeof(int)); // Dynamically allocate memory

    if (mergedArr == NULL) {
        printf("Memory allocation failed!\\n");
        return 1;
    }

    // Step 4: Call the merge function
    mergeSortedArrays(arr1, n1, arr2, n2, mergedArr);

    // Step 5: Print the merged array
    printf("Merged array: ");
    for (int i = 0; i < n_merged; i++) {
        printf("%d ", mergedArr[i]);
    }
    printf("\\n");

    free(mergedArr); // Free dynamically allocated memory
    return 0;
}

Run

• Sample Output:

Merged array: 1 2 3 4 5 6 7 8 9

 

• Stepwise Explanation:

1. Initialization: Three integer pointers i, j, and k are initialized to 0. i tracks arr1, j tracks arr2, and k tracks mergedArr.
2. Main Loop (while (i < n1 && j < n2)): This loop continues as long as there are elements left in both arr1 and arr2.
   • It compares arr1[i] and arr2[j].

• The smaller element is copied to mergedArr[k], and its respective pointer (i or j) is incremented, along with k.

1. Handle Remaining Elements (while (i < n1) and while (j < n2)): After the main loop, one of the arrays might still have remaining elements (if they were of different lengths). These loops simply copy any leftover elements from arr1 or arr2 into mergedArr. Since the original arrays were sorted, these remaining elements are already in their correct order relative to each other.
2. Memory Management: Dynamic memory malloc is used for mergedArr to accommodate its size, and free is used to release the memory after use.

Approach 2: Naive Approach (Concatenate and Sort)

This approach is simpler to implement but generally less efficient for large arrays compared to the two-pointer method, as it involves a full sort operation on the combined array.

• One-line summary: Copy all elements from both input arrays into a single larger array, then sort this combined array.

 

// Merge Two Sorted Arrays (Concatenate and Sort)
#include <stdio.h>
#include <stdlib.h> // Required for malloc
#include <string.h> // Required for memcpy
// For qsort
#include <stdbool.h>

// Comparison function for qsort
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int arr1[] = {1, 3, 5, 7};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);

    int arr2[] = {2, 4, 6, 8, 9};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);

    int n_merged = n1 + n2;
    int *mergedArr = (int *)malloc(n_merged * sizeof(int)); // Dynamically allocate memory

    if (mergedArr == NULL) {
        printf("Memory allocation failed!\\n");
        return 1;
    }

    // Step 1: Copy elements from arr1 to mergedArr
    memcpy(mergedArr, arr1, n1 * sizeof(int));

    // Step 2: Copy elements from arr2 to mergedArr, starting after arr1's elements
    memcpy(mergedArr + n1, arr2, n2 * sizeof(int));

    // Step 3: Sort the entire merged array
    qsort(mergedArr, n_merged, sizeof(int), compare);

    // Step 4: Print the merged array
    printf("Merged array (Naive Approach): ");
    for (int i = 0; i < n_merged; i++) {
        printf("%d ", mergedArr[i]);
    }
    printf("\\n");

    free(mergedArr); // Free dynamically allocated memory
    return 0;
}

Run

• Sample Output:

Merged array (Naive Approach): 1 2 3 4 5 6 7 8 9

 

• Stepwise Explanation:

1. Memory Allocation: A new array mergedArr is allocated to hold all elements from both input arrays.
2. Concatenation: Elements from arr1 are copied into the beginning of mergedArr. Then, elements from arr2 are copied starting from the position immediately after arr1's elements.
3. Sorting: The qsort standard library function is used to sort mergedArr. This is typically an O(N log N) operation, where N is the total number of elements.
4. Memory Management: Dynamic memory malloc is used for mergedArr, and free is used to release it.

Conclusion

Merging two sorted arrays is a common task with practical applications. The Two-Pointer Approach is generally preferred due to its optimal time complexity (O(n1 + n2)), making it very efficient. While the Naive Approach (concatenate and sort) is simpler to code, its higher time complexity (O(N log N) where N is total elements) makes it less suitable for performance-critical scenarios. Understanding the two-pointer technique is essential for efficient algorithm design.

Summary

• Problem: Combine two sorted arrays into a single sorted array.
• Optimal Solution: Two-Pointer Approach.
• Iteratively compare elements from both arrays.
• Place the smaller element into the result array.
• Handle remaining elements from the longer array.
• Time Complexity: O(n1 + n2) – linear, very efficient.
• Alternative Solution: Concatenate and Sort.
• Copy all elements into a new array.
• Use a sorting algorithm (like qsort) to sort the combined array.
• Time Complexity: O(N log N) – less efficient for large N compared to the two-pointer method.
• Use Cases: Merge Sort, database operations, data stream processing.

Quiz & Call to Action

Quiz Question: Given arrA = [10, 20, 30] and arrB = [15, 25], what would be the state of the merged array after the first iteration of the main while loop using the Two-Pointer Approach?

Call to Action: Try implementing the mergeSortedArrays function yourself, but this time, modify it to merge three sorted arrays! Share your solution and insights in the comments below.