The C language implements the method of combining an array B on an array A

In this paper, the example of C language on the array A to achieve an orderly combination of array B method, to share with you for your reference. Specific analysis is as follows:

Subject: array A and array B are ordered. Array A has enough memory to hold array B. Merge array B into array A

Analysis: if merge from front to back, the complexity will be O(N2), this complexity is obviously not the optimal solution, using two Pointers to the end of the two arrays, from back to forward traversal, this complexity is O(N2).

From this you can write the following code:

#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

int arrayA[10] = {1, 3, 5, 7, 9};
int arrayB[] = {2, 4, 6, 8, 10};
const int sizeB = sizeof arrayB / sizeof *arrayB;
const int sizeA = sizeof arrayA / sizeof *arrayA - sizeB;

int* mergeArray(int *arrayA, int sizeA, int *arrayB, int sizeB)
{
 if (arrayA == NULL || arrayB == NULL || sizeA < 0 || sizeB < 0)
 return NULL;

 int posA = sizeA - 1;
 int posB = sizeB - 1;

 while (posA >= 0 && posB >= 0)
 {
 if (arrayA[posA] < arrayB[posB])
 {
  arrayA[posA + posB + 1] = arrayB[posB];
  posB--;
 }
 else
 {
  arrayA[posA + posB + 1] = arrayA[posA];
  posA--;
 }
 copy(arrayA, arrayA + 10, ostream_iterator<int>(cout, " "));
 system("pause");
 }

 return arrayA;
}

void main()
{
 int *result = mergeArray(arrayA, sizeA, arrayB, sizeB);

 copy(result, result + 10, ostream_iterator<int>(cout, " "));
 cout << endl;
}

After the code is written, it seems to complete the required function, but there is more than that, you must do UT for the above code

1. The robustness

ArrayA or arrayB are null and have a length less than 0

2. Boundary use cases

ArrayA is null with length 1; ArrayB is not empty, and its length is greater than 1
The first element use case
Const int size = 6;
Int arrayA [size] = {2};
Int arrayB[] = {0, 1, 1, 1, 1};
And vice
Const int size = 6;
Int arrayA[size] = {0, 1, 1, 1, 1};
Int arrayB [] = {2};

3. Normal use case:

Const int size = 10;
Int arrayA[size] = {1, 3, 5, 7, 9};
Int arrayB[] = {2, 4, 6, 8, 10};

Const int size = 10;
Int arrayA[size] = {2, 4, 6, 8, 10};
Int arrayB[] = {1, 3, 5, 7, 9};

Const int size = 10;
Int arrayA[size] = {1, 2, 3, 4, 5};
Int arrayB[] = {6, 7, 8, 9, 10};

Const int size = 10;
Int arrayA[size] = {6, 7, 8, 9, 10};
Int arrayB[] = {1, 2, 3, 4, 5};

After the above test, it is not difficult to find that in the boundary condition use case, the code can no longer run the result correctly. Driven by the test case, it is not difficult to write the correct code as follows:

int* mergeArray(int *arrayA, int sizeA, int *arrayB, int sizeB)
{
 if (arrayA == NULL || arrayB == NULL || sizeA < 0 || sizeB < 0)
 return NULL;

 int posA = sizeA - 1;
 int posB = sizeB - 1;

 while (posA >= 0 && posB >= 0)
 {
 if (arrayA[posA] < arrayB[posB])
 {
  arrayA[posA + posB + 1] = arrayB[posB];
  posB--;
 }
 else
 {
  arrayA[posA + posB + 1] = arrayA[posA];
  posA--;
 }
 copy(arrayA, arrayA + size, ostream_iterator<int>(cout, " "));
 system("pause");
 }

 //There are two scenarios:
 //1. posA < 0 && posB >= 0
 //2. posA >= 0 && posB < 0
 //Only case 1 needs to be dealt with
 if (posA < 0 && posB >= 0)
 {
 while (posB >= 0)
 {
  arrayA[posA + posB + 1] = arrayB[posB];
  posB--;
 }
 } 
 return arrayA;
}

It is believed that this paper has certain reference value to the learning of C program algorithm design.