Reputation: 41
I have 2 sorted arrays A[], B[]. My requirement is to merge this 2 sorted arrays and resultant array also should be in sorted manner. Since there is 2 sorted array I have 2 methods to solve this. One is using MERGE SORT method I can sort & another one I suggest is simply joining this 2 arrays and sorting the resultant array by quick sort method.
My question is in above two methods which one will have more efficiency , less run time , more stable. Please give me suggestion & also if there is any other solution is available please let me know.
Upvotes: 1
Views: 160
Reputation: 15915
Merging two pre-sorted arrays require only O(N)
time and O(N)
extra space where N = n + m
. Here n
and m
are number of elements in each array.
In above case, if the two arrays are unsorted initially, you have to sort them in O(nlogn)
and O(mlogm)
time respectively. Then merging them require another O(N)
time resulting in total O(max(m, n) log max(m, n))
time asymptotically.
On the other side, if you join the two array and apply any first sorting algorithm like quicksort (C++'s sort(..)
) the time complexity will be O(NlogN)
and with O(N)
extra space.
So it terms of time complexity, I think you should use merging method of merge sort as your two arrays are sorted initially.
Upvotes: 1
Reputation: 25286
Not using classes, i.e. pure C:
void merge(int A[], int B[], int C[])
{
int a, b, c;
a= b= c= 0;
while (a<50 && b<50) {
if (A[a] < B[b])
C[c++]= A[a++];
else C[c++]= B[b++];
}
while (a<50) C[c++]= A[a++];
while (b<50) C[c++]= B[b++];
}
Upvotes: 0
Reputation: 21038
With pre-sorted arrays, the simplest method should be something like
int A[50];
int B[50];
int C[100];
std::merge(std::begin(A), std::end(A), std::begin(B), std::end(B), std::begin(C));
Or if you're using std::array
s
std::array<int, 50> A;
std::array<int, 50> B;
std::array<int, 100> C;
std::merge(A.begin(), A.end(), B.begin(), B.end(), C.begin());
Upvotes: 4