Merge two sorted arrays using the C programming language

Merge two sorted arrays using the C programming language

Code:

#include <stdio.h>

void mergeArrays(int arr1[], int m, int arr2[], int n, int result[]) {
int i = 0, j = 0, k = 0;

while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}

while (i < m) {
result[k++] = arr1[i++];
}

while (j < n) {
result[k++] = arr2[j++];
}
}

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

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

int merged[m + n];

mergeArrays(arr1, m, arr2, n, merged);

printf("Merged array: ");
for (int i = 0; i < m + n; i++) {
printf("%d ", merged[i]);
}

return 0;
}

 

In this example, mergeArrays is a function that takes two sorted arrays (arr1 and arr2), their sizes (m and n), and an array to store the merged result. The function iterates through the two input arrays while comparing their elements and placing them in the merged result array in sorted order.

The main function demonstrates how to use the mergeArrays function. It defines two sorted arrays, calculates their sizes, creates an array to hold the merged result, calls the mergeArrays function, and then prints the merged array.

Remember that this code assumes that both input arrays are already sorted. If the arrays are not sorted, the merging process won't produce the correct result.

Explanation:

#include <stdio.h>

This line includes the standard input-output library, which contains functions like printf and scanf.

void mergeArrays(int arr1[], int m, int arr2[], int n, int result[]) {

Here, we define a function named mergeArrays that takes in five arguments: two integer arrays (arr1 and arr2), their respective sizes (m and n), and an integer array (result) to store the merged result.

int i = 0, j = 0, k = 0;

Declare three integer variables i, j, and k, which will be used as indices for iterating through arr1, arr2, and result, respectively.

while (i < m && j < n) {

This initiates a while loop that continues as long as the indices i are less than m (size of arr1) and j are less than n (size of arr2), ensuring that we haven't reached the end of either array.

if (arr1[i] < arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}

Inside the loop, this if-else block compares the elements at the current indices i and j in arr1 and arr2, respectively. The smaller element is placed in the result array at index k, and the corresponding index (i or j) is incremented to move to the next element. The index k is also incremented to place the next element in the result array.

}

This closes the while loop that compares and merges elements from the two arrays.

while (i < m) {
result[k++] = arr1[i++];
}

After merging elements from both arrays, there might be remaining elements in either arr1 or arr2. This while loop handles any remaining elements in arr1 by copying them directly into the result array.

while (j < n) {
result[k++] = arr2[j++];
}

Similarly, this while loop handles any remaining elements in arr2 by copying them into the result array.

}

This marks the end of the mergeArrays function definition.

int main() {

The main function is the entry point of the program.

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

We define an integer array arr1 with sorted elements. The size m of arr1 is calculated by dividing the total size of the array by the size of its first element. This is a common technique to find the number of elements in an array.

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

Similarly, we define another integer array arr2 with sorted elements and calculate its size n.

int merged[m + n];

We declare an integer array merged to hold the merged result. Its size is the sum of m and n, which is the maximum possible size of the merged array.

mergeArrays(arr1, m, arr2, n, merged);

Here, we call the mergeArrays function with the two input arrays arr1 and arr2, their sizes m and n, and the merged array to store the result.

printf("Merged array: ");
for (int i = 0; i < m + n; i++) {
printf("%d ", merged[i]);
}

This loop iterates through the merged array and prints each element, resulting in the merged and sorted array.

return 0;
}

Finally, the main function returns 0 to indicate successful completion of the program.

 

Algorithm:

Input:

• Two sorted integer arrays arr1 and arr2 with sizes m and n respectively.

Output:

• Merged and sorted integer array result.

Algorithm Steps:

1. Initialize three integer variables i, j, and k to keep track of indices in arr1, arr2, and result arrays respectively. Set them to 0 initially.

2. Start a loop while i is less than m and j is less than n:

   • Compare arr1[i] and arr2[j].

   • If arr1[i] is smaller, add it to result[k] and increment both i and k.

   • If arr2[j] is smaller or equal, add it to result[k] and increment both j and k.

3. If there are any remaining elements in arr1, copy them to result array using a loop until i reaches m.

4. If there are any remaining elements in arr2, copy them to result array using a loop until j reaches n.

5. The mergeArrays function is now complete.

Main Program:

1. Declare two sorted integer arrays arr1 and arr2.

2. Calculate the sizes m and n of arr1 and arr2 respectively.

3. Create an integer array merged with a size of m + n to store the merged result.

4. Call the mergeArrays function with arr1, m, arr2, n, and merged as arguments.

5. Iterate through the merged array and print each element.

6. End the program by returning 0 from the main function.

The algorithm ensures that the merged array is sorted because we're comparing elements from the two arrays while merging, and always selecting the smaller element to put into the result array. This way, the resulting array maintains the sorted order of the original arrays.

 

Time Complexity:

The time complexity of the above C program to merge two sorted arrays is O(m + n), where 'm' is the size of the first array (arr1) and 'n' is the size of the second array (arr2).

Let's break down the major parts of the program that contribute to this time complexity:

1. Merging Loop: The primary loop that merges the two arrays runs as long as 'i' is less than 'm' and 'j' is less than 'n'. In the worst case, where each element of both arrays is compared and placed in the merged array, this loop will run a total of 'm + n' times.

2. Remaining Elements: After the merging loop, there might be remaining elements in either arr1 or arr2. The two separate while loops that copy these remaining elements also run at most 'm' or 'n' times respectively.

Combining these components, the overall time complexity is determined by the largest of 'm' and 'n', resulting in a complexity of O(m + n).

It's important to note that this is an optimal time complexity for merging two sorted arrays because you need to examine each element at least once to ensure the sorted order is preserved in the merged array.

 

Space Complexity:

The space complexity of the above C program to merge two sorted arrays is O(m + n), where 'm' is the size of the first array (arr1) and 'n' is the size of the second array (arr2).

Here's how the space complexity is broken down:

1. Input Arrays (arr1 and arr2): The space used by these arrays is directly proportional to their sizes 'm' and 'n', which contributes O(m + n) to the space complexity.

2. Merged Array (merged): An additional array is created to store the merged result. This array has a size of 'm + n', which also contributes O(m + n) to the space complexity.

3. Loop Variables (i, j, and k): These variables take up constant space regardless of the size of the input arrays. Therefore, their space contribution is O(1).

4. Function Arguments and Local Variables: The function arguments (arr1, m, arr2, n, and result) and local variables (i, j, k) also occupy constant space, which adds to the overall constant space overhead.

Combining these components, the dominant factor in the space complexity is the size of the merged array (m + n), resulting in a space complexity of O(m + n).

It's worth noting that the space complexity doesn't depend on the sizes of the input arrays alone; it's determined by the size of the merged result, which is the maximum size among the input arrays' sizes.

Thank You