1 /*
 2  *Author: ZhangHaiba
 3  *Date: 2014-1-23
 4  *File: ordered_array_merge.c
 5  *
 6  *a demo shows merge algorithm in two ordered array
 7  */
 8 
 9 #include <stdio.h>
10 #define LEN 512
11 #define INF 0x7fffffff;
12 
13 //public
14 int array_merge1(int dest[], int src_a[], int a_len, int src_b[], int b_len);
15 int array_merge2(int deet[], int src_a[], int a_len, int src_b[], int b_len);
16 void show_array(int a[], int n);
17 
18 
19 int main(void)
20 {
21     int a[] = {43, 53, 67, 69, 90, 134, 153};
22     int b[] = {12, 34, 44, 57, 70, 88, 245, 443, 663, 766};
23     int a_len = sizeof(a) / sizeof(a[0]);
24     int b_len = sizeof(b) / sizeof(b[0]);
25     int c[LEN], d[LEN];
26 
27 
28     int c_len = array_merge1(c, a, a_len, b, b_len);
29     show_array(c, c_len);
30     int d_len = array_merge2(d, a, a_len, c, c_len);
31     show_array(d, d_len);
32     return 0;
33 }
34 
35 
36 int array_merge1(int *c, int *a, int a_len, int *b, int b_len)
37 {
38     int i = 0, j = 0, k = 0;
39 
40     while (i < a_len && j < b_len)
41         c[k++] = a[i] < b[j] ? a[i++] : b[j++];
42     while (i < a_len)
43         c[k++] = a[i++];
44     while (j < b_len)
45         c[k++] = b[j++];
46     return k;
47 }
48 
49 int array_merge2(int *c, int *a, int a_len, int *b, int b_len)
50 {
51     int i = 0, j = 0, k = 0;
52 
53     a[a_len] = b[b_len] = INF; //set sentinel
54     while (i < a_len || j < b_len)
55         c[k++] = a[i] < b[j] ? a[i++] : b[j++];
56     return k;
57 }
58 
59 void show_array(int *a, int n)
60 {
61     int i;
62 
63     for (i = 0; i < n; ++i)
64         printf(i == n-1 ? "%d\n" : "%d ", a[i]);
65 }

ZhangHaiba-MacBook-Pro:code apple$ ./a.out
12 34 43 44 53 57 67 69 70 88 90 134 153 245 443 663 766
12 34 43 43 44 53 53 57 67 67 69 69 70 88 90 90 134 134 153 153 245 443 663 766