Merge Two Sorted Arrays in-place

Posted in

Merge Two Sorted Arrays in-place

Vinay Khatri
Last updated on June 10, 2022

    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:

    Tags:
    array sorting

    Leave a Comment on this Post

    0 Comments