Here is the C code to merge two array of same size (they could be of different size also). Merge procedure is the heart of merge sort algorithm.

To understand data structure and algorithm, you can read this book by Sahni Horowitz.

**How Does Merge Procedure Work?**

See the figure above. In Merge Procedure, the first element of array A(left side in the figure) and array B(right side in the figure) is compared, whichever is smaller goes to the newly created array C (the below array in the figure).

In our case, 2 and 1 is compared, 1 makes into the newly created array. In next iteration, 2 and 2 and 3 is compared, 2 makes into the array. Next, 3 and 8 is compared and so on and so forth till elements of both the array are inserted into the newly created array.

**Time Complexity: O(m+n) = O(n)** (Assuming that first array is of size *m* and second array is of size *n*)

**Space Complexity: O(n)** (Because a new array has to be created of size *m+n = n*)

void merge(int* a, int p, int q, int r){ int n1 = q-p+1, n2 = r-q, i, j, k; int L[n1], R[n2]; for(i=0;i<n1;i++) L[i] = a; for(j=0;j<n2;j++) R[j] = a[q+j+1]; i=0;j=0;k=p; while(i<n1 && j<n2){ if(L[i]<R[j]){ a[k] = L[i++]; } else{ a[k] = R[j++]; } k++; } while(i<n1){ a[k] = L[i++]; k++; } while(j<n2){ a[k] = R[j++]; k++; } }

Viewers are advised to write the driver program themselves

To understand pointers in C, you may refer this book. This book explains 2D and 3D pointer in great detail.