CODEWITHSUNDEEP
c++calgorithmsortingdata-structures
xxxxxxxxxx
xxxxxxxxxx

Reputation: 41

Data Structures - choosing sorting method

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

Answers (3)

Kaidul
Kaidul

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

Paul Ogilvie
Paul Ogilvie

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

user657267
user657267

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::arrays

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

Related Questions