#include <iostream>
#include <string.h>
using namespace std;

//base:array1d的实际空间长度等于两个数组长度之和

//空间复杂度O(n)，即归并排序
void merge1(int *array1, int len1, int *array2, int len2)
{
    int *arrayTmp = new int[len1];
    memcpy(arrayTmp, array1, len1 * sizeof(int));
    
    int p1 = 0;
    int p2 = 0;
    int pTmp = 0;
    while (p1 < len1 && p2 < len2)
    {
        array1[pTmp++] = arrayTmp[p1] < array2[p2] ? arrayTmp[p1++] : array2[p2++];
    }
    
    if (p1 < len1)
    {
       memcpy(array1 + pTmp, arrayTmp + p1, (len1 - p1) * sizeof(int)); 
    }
    
    if (p2 < len2)
    {
        memcpy(array1 + pTmp, array2 + p2, (len2 - p2) * sizeof(int));
    }
    
    delete arrayTmp;
}

//空间复杂度O(1)，双指针，array1后面都是占位的0，因此从数组的最后一位开始遍历，从大往小，开始放值
void merge2(int *array1, int len1, int * array2, int len2)
{
    int p1 = len1 - 1;
    int p2 = len2 - 1;
    int p = len1 + len2 -1;
    
    while (p1 >= 0 && p2 >= 0)
    {
        array1[p--] = array1[p1] > array2[p2] ? array1[p1--] : array2[p2--];
    }
    
    if (p2 >= 0)
    {
        memcpy(array1, array2, (p2 + 1) * sizeof(int));
    }
    
}

int main() {
    int a1[10] = {0,1,3,5,7,9,0,0,0,0};
    int a2[4] = {2,4,6,8};
    
    //int a1[10] = {2,3,0,0,0,0,0,0,0,0};
    //int a2[8] = {0,1,4,5,6,7,8,9};
    
    //merge1(a1, 2, a2, 8);
    merge2(a1, 6, a2, 4);
    
    for (int i = 0; i < 10; i++)
        cout << a1[i] << endl;
        
    return 0;
}