Algorithm to merge sorted arrays

Program to merge two sorted arrays

// m - size of A

// n - size of B

// size of C array must be equal or greater than

// m + n

void merge(int m, int n, int A[], int B[], int C[]) {

      int i, j, k;

      i = 0;

      j = 0;

      k = 0;

      while (i < m && j < n) {

            if (A[i] <= B[j]) {

                  C[k] = A[i];

                  i++;

            } else {

                  C[k] = B[j];

                  j++;

            }

            k++;

      }

      if (i < m) {

            for (int p = i; p < m; p++) {

                  C[k] = A[p];

                  k++;

            }

      } else {

            for (int p = j; p < n; p++) {

                  C[k] = B[p];

                  k++;

            }

      }

}

Complexity analysis

Merge algorithm's time complexity is O(n + m). Additionally, it requires O(n + m) additional space to store resulting array.