Merge sorted array

Given two sorted arrays of size m and n respectively. How to merge them together? Write the code.

C++:
01 int* merge(int* A, int* B, int m, int n)
02 {
03     int *C=new int[m+n];
04     int p=0;
05     int q=0;
06     int t=0;
07     while(true){
08         if(A[p]<=B[q])
09             C[t++]=A[p++];
10         else
11             C[t++]=B[q++];
12         if(p==m){
13             while(q<n)
14                 C[t++]=B[q++];
15             return C;
16         }
17         if(q==n){
18             while(p<m)
19                 C[t++]=A[p++];
20             return C;
21         }
22     }
23 }
What if m>>n? We could add elements in B into A using binary search. The complexity is O(nlogm).
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s