Given two sorted integer array 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.

Difficulty: Easy

The basic idea is to fill up the array A from the end (from k = m + n – 1) to avoid *memmove* or *memcpy *operations. We walk through each array one by one from the end (m –1 and n – 1) as well and copy greater one to k position. Then moving to the next element.

A[k–] = A[i] > B[j] ? A[i–] : B[j–];

When we reach to j= 0 condition, it means that we ends up populating every empty space in A. j != 0 means that the rest of elements in B is less or equal than the smallest element in A, i.e. A[0]. We should copy the rest of elements in B to A.

while( j >= 0 ) A[k–] = B[j–];

The final code looks like this:

void merge(int* A, int m, int* B, int n) {
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while ( i >= 0 && j >= 0 ) {
A[k--] = A[i] > B[j] ? A[i--] : B[j--];
}
while( j >= 0 ) A[k--] = B[j--];
}

*-The question is from https://leetcode.com/problems/merge-sorted-array/*

### Like this:

Like Loading...

*Related*