#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int merge(int* ar1, int len1, int* ar2, int len2, int** rtn)
/*++
 DeScription:
    This routine merge two sorted arrays into one sorted array,
    the same values in different arrays will be keeped.

Arguments:
    ar1 - The first sorted array to be merged
    len1 - The num of items in ar1
    ar2 - The second sorted array to be merged
    len2 - The num of items in ar2
    rtn - The caller proviced pointer to get the result array,
        memory allocated for rtn should be free by the caller.

Return Value:
    The num of items in the merge array
--*/
{
    int i=0,j=0,k=0;
    int m=0;
    int* res = NULL;

    if (ar1 == NULL || ar2 == NULL || rtn == NULL) {
        return 0;
    }

    *rtn = (int *)malloc((len1+len2)*sizeof(int));
    if(*rtn == NULL) {
        return 0;
    }
    memset(*rtn, 0, (len1+len2)*sizeof(int));
    res = (int*)*rtn;

    while(i<len1 && j<len2) {
        if (ar1[i]<=ar2[j]) {
            res[k++] = ar1[i++];
        } else {
            res[k++] = ar2[j++];
        }
    }

    while(i<len1) {
        res[k++] = ar1[i++];
    }
    while(j<len2) {
        res[k++] = ar2[j++];
    }

    return  len1+len2;
}

int merge_test()
{
    int a1[] = {0,1,2,5,8,19,34,43,52};
    int a2[] = {1,4,5,12,17,33,42,51,53,65,76};
    int len1 = sizeof(a1)/sizeof(int);
    int len2 = sizeof(a2)/sizeof(int);
    int i = 0, len = 0;
    int* a3 = NULL;
    int* ptr = NULL;

    len = merge(a1, len1, a2, len2, &a3);
    if (a3 == NULL) {
        printf("a3==NULL\n");
        return 1;
    }

    ptr = a3;
    while(i<len) {
        printf("a3[%3d]---->%8d\n", i++, *ptr++);   
    }

    if (a3 != NULL) {
        free(a3);
    }

    return 0;
}

int main(int argc, char* argv[])
{
    merge_test();

    return 0;
}