Problem discription

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:

You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Accpted Code 1 ( use extra space)

1 class Solution { 2 public: 3     void merge(int A[], int m, int B[], int n) { 4         // we use "ai" and "bi" to keep trace  5         // of array A[] and B[] respectively 6         // "ci" holds the number of elements that  7         // has been merged 8         int ai = 0, bi = 0, ci = 0; 9         // create an extra vector of size n+m 10         // to keep the sorted array11         vector
     
       C(n + m);12         while (ci < n + m) {13             // from small to large 14             if (ai < m && (bi >= n || A[ai] <= B[bi])) {15                 C[ci++] = A[ai++];16             } else {17                 C[ci++] = B[bi++];18             }19         }20         // copy the sorted array from C to A21         for (int i = 0; i < n+m; i++) A[i] = C[i];22     }23 };
     

Accepted Code (without extra space) Clear & Simple

1 class Solution { 2 public: 3     void merge(int A[], int m, int B[], int n) { 4         // we use "ai", "bi" to iterator A[] and B[]  5         // from the end respectively 6         // since the size of A[] equal to or greater n+m 7         // thus we can use inplace sort by filling A[] 8         // from A[n+m-1] to A[0] 9         int ai = m - 1, bi = n - 1, ci = n + m - 1;10         while (ci >= 0) {11             if (ai >= 0 && (bi < 0 || A[ai] >= B[bi])) {12                 A[ci--] = A[ai--];13             } else {14                 A[ci--] = B[bi--];15             }16         }17     }18 };