Merge Two Sorted Arrays in-place

Problem

Two integer arrays nums1 and nums2 are sorted in non-decreasing order, and two integers m and n are supplied representing the number of integers in nums1 and nums2 correspondingly. In a single pass, merge nums1 and nums2 into a single array. The final classified array should be kept inside the array nums1 rather than returned by the function. To do this, nums1 has a length of m + n where the elements of the first m indicate the items of nums1 . The length of nums2 is n .

Brute force approach

We can copy all the elements of nums2 into nums1 and then sort the entire array. This is an easy yet inefficient solution as this is not in-place and takes O(( m + n )log( m + n )) time.

Efficient Approach

We can follow a 3 pointers approach. We place one pointer at the ending element of the first array and the second pointer at the ending element of the second array. Let’s say pointers are one and two respectively. The third pointer tells the next available index to place the element. This is initialized to the ( size of nums1 -1) . Let’s call this variable as finish . We then compare these two elements. If nums1 [one] >= nums2 [two] , we  place this element at the last index of nums1 and decrease finish and vice versa. We do this until all the pointers are greater than or equal to 0.   This is an in-place solution and takes O( m + n ) time.

C++

#include <iostream>
#include <algorithm>
using namespace std;
 void solve(int a[], int b[], int m, int n)
{

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

        if (a[i] > b[0])
        {
            swap(a[i], b[0]);
            int first = b[0];
 
            int k;
            for (k = 1; k < n && b[k] < first; k++) {
                b[k - 1] = b[k];
            }
 
            b[k - 1] = first;
        }
    }
}
 
int main()
{
    int a[] = { 1, 3, 4, 5 };
    int b[] = { 2, 3, 10 };
 
    int m = sizeof(a) / sizeof(a[0]);
    int n = sizeof(b) / sizeof(b[0]);
 
    solve(a, b, m, n);
 
for(int i=0;i<m;i++) cout<<a[i]<<" ";
cout<<"\n";
for(int i=0;i<n;i++) cout<<b[i]<<" ";
 
    return 0;
}

Python

def solve(a, b):
 
    m = len(a)
    n = len(b)
    for i in range(m):
 
        if a[i] > b[0]:
            temp = a[i]
            a[i] = b[0]
            b[0] = temp
 
            first = b[0]
            k = 1
            while k < n and b[k] < first:
                b[k - 1] = b[k]
                k = k + 1
 
            b[k - 1] = first
 
a = [1, 4, 7, 8, 10]
b = [2, 3, 9]
 
solve(a, b)
 
print(a)
print(b)

C

void solve(int a[], int b[], int m, int n)
{

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

        if (a[i] > b[0])
        {
            int temp = a[i];
            a[i]=b[0];
            b[0]=temp;
            int first = b[0];
 

            int k;
            for (k = 1; k < n && b[k] < first; k++) {
                b[k - 1] = b[k];
            }
 
            b[k - 1] = first;
        }
    }
}
 
int main()
{
    int a[] = { 1, 3, 4, 5 };
    int b[] = { 2, 3, 10 };
 
    int m = sizeof(a)/sizeof(a[0]);
    int n = sizeof(b)/sizeof(b[0]);
 
    solve(a, b, m, n);
 
for(int i=0;i<m;i++) printf("%d ",a[i]);
printf("\n");
for(int i=0;i<n;i++) printf("%d ",b[i]);
 
    return 0;
}

Output

[1, 2, 3, 4, 7]
[8, 9, 10]

People are also reading:

• WAP to Count no. of alphabets, digits and spaces present in a file
• The Stock Span Problem
• Find maximum of minimum for every window size in a given array
• WAP to Print Triangle Using * Character
• Find ancestors of a given node in a Binary Tree
• Subset Sum Problem
• Maximum size square sub-matrices with all 1’s
• Merge Sort for Linked Lists
• Move all zeros present in an array to the end
• Program to Find LCM and HCF of two numbers