Merge these two sorted arrays without using a third array

Solution

#include <iostream>

#include <algorithm>

#include <iomanip>

#include <string>

using namespace std;

// assume the actual size of arr2 is size1 + size2

void MergeSortedArrays(int* arr1, int size1, int *arr2, int size2)

{

int* p1 = arr1 + size1 - 1;

int* p2 = arr2 + size2 - 1;

int* p3 = p2 + size1;

while(p1 >= arr1 && p2 >= arr2){

if(*p1 > *p2){

*p3 -- = *p1 --;

}

else{

*p3 -- = *p2 --;

}

}

while(p1 >= arr1){

*p3 -- = *p1 --;

}

}

void InitArray(int **arr, int s, int max)

{

int* p = new int[s];

*arr = p;

for(int i = 0; i < s; ++i){

*p ++ = rand() % max;

}

sort(*arr, *arr + s);

}

void PrintArray(int *arr, int s, string msg)

{

cout << msg << endl;

for(int i = 0; i < s; ++ i){

cout << setw(4) << arr[i];

}

cout << endl;

}

int main(int argc, char* argv[])

{

srand(1);

for(int i = 0; i < 5; i++){

int *arr1, *arr2;

int size1, size2;

size1 = rand() % 20 + 1;

size2 = rand() % 20 + 1;

InitArray(&arr1, size1, 20);

PrintArray(arr1, size1, "Array 1: ");

InitArray(&arr2, size1 + size2, 40);

PrintArray(arr2, size2, "Array 2: ");

MergeSortedArrays(arr1, size1, arr2, size2);

PrintArray(arr2, size1 + size2, "After merging: ");

cout << endl;

delete arr1;

delete arr2;

}

return 0;

}

Output

Array 1:

0 14

Array 2:

1 2 4 9 24 25 25 27

After merging:

0 1 2 4 9 14 24 25 25 27

Array 1:

2 15

Array 2:

4 6 7 12 15 21 22 22 27 31 33 36

After merging:

2 4 6 7 12 15 15 21 22 22 27 31 33 36

Array 1:

2 3 4 7 9 11 12 13 13 14 15 19

Array 2:

0 2 3 4 5 6 6 8 8 9 9 10 10 13 18 19 21 21 22

After merging:

0 2 2 3 3 4 4 5 6 6 7 8 8 9 9 9 10 10 11 12 13 13 13 14 15 18 19 19 21 21 22

Array 1:

8 9

Array 2:

0 3 4 6 11 16 17 18 23 24 26 28 34 36

After merging:

0 3 4 6 8 9 11 16 17 18 23 24 26 28 34 36

Array 1:

1 13 15

Array 2:

4 10 17 18 21 24 25 26 26 30

After merging:

1 4 10 13 15 17 18 21 24 25 26 26 30

Press any key to continue . . .