#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.
#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.
Input:
arr1
and arr2
with sizes m
and n
respectively.Output:
result
.Algorithm Steps:
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.
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
.
If there are any remaining elements in arr1
, copy them to result
array using a loop until i
reaches m
.
If there are any remaining elements in arr2
, copy them to result
array using a loop until j
reaches n
.
The mergeArrays
function is now complete.
Main Program:
Declare two sorted integer arrays arr1
and arr2
.
Calculate the sizes m
and n
of arr1
and arr2
respectively.
Create an integer array merged
with a size of m + n
to store the merged result.
Call the mergeArrays
function with arr1
, m
, arr2
, n
, and merged
as arguments.
Iterate through the merged
array and print each element.
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.
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:
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.
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.
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:
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.
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.
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).
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