Merge Sorted Array

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–];

image

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/

Advertisements
This entry was posted in Algorithms, Technical Interview and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s