Merge Sorted Array - C Solution

1. Introduction

Merging two sorted arrays is a common problem in computer programming. It involves combining two sorted arrays into one larger array while maintaining the sorted order. This is a fundamental concept in data structure and algorithms, often used in sorting algorithms like merge sort.

Problem

Given two arrays, array1, and array2, which are sorted in ascending order, the task is to merge these arrays into a single sorted array.

2. Solution Steps

1. Initialize three variables to track the current index of array1, array2, and the merged array.

2. Compare elements of array1 and array2 at the current indices.

3. Add the smaller element to the merged array and move the corresponding index forward.

4. If one array is fully traversed, add all remaining elements of the other array to the merged array.

5. Continue until all elements are merged into the new array.

3. Code Program

#include <stdio.h>

void mergeSortedArrays(int array1[], int n1, int array2[], int n2, int mergedArray[]) {
    int i = 0, j = 0, k = 0;

    // Merging arrays
    while (i<n1 && j <n2) {
        if (array1[i] < array2[j]) {
            mergedArray[k++] = array1[i++];
        } else {
            mergedArray[k++] = array2[j++];
        }
    }

    // Copy remaining elements of array1, if any
    while (i < n1) {
        mergedArray[k++] = array1[i++];
    }

    // Copy remaining elements of array2, if any
    while (j < n2) {
        mergedArray[k++] = array2[j++];
    }
}

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

    mergeSortedArrays(array1, n1, array2, n2, mergedArray);

    printf("Merged Array: ");
    for (int i = 0; i < n1 + n2; i++) {
        printf("%d ", mergedArray[i]);
    }

    return 0;
}

Output:

Merged Array: 1 2 3 4 5 6 7 8

Explanation:

1. int array1[] = {1, 3, 5, 7}; and int array2[] = {2, 4, 6, 8}; - Define two sorted arrays.

2. int mergedArray[n1+n2]; - Create an array to store the merged result.

3. mergeSortedArrays(array1, n1, array2, n2, mergedArray); - Call the function to merge the arrays.

4. Inside mergeSortedArrays, loop through both arrays and add the smaller element to mergedArray.

5. If one array is completely traversed, the remaining elements of the other array are added.

6. The main function prints the merged array, which is sorted.