We have two sorted arrays of integers. Without using additional memory we need to merge these two arrays such that the smallest numbers are in the 1st array and the remaining numbers are in the second array.

For instance, if your two arrays are $A=[1,3,9,14]$ and $B=[2,4,15]$, the result should be $A=[1,2,3,4], B=[9,14,15]$. Entries are integers, and you can use only $O(1)$ extra memory for auxiliary variables.

  • $\begingroup$ Just to clarify, if your two arrays are $A=[1,3,9,14]$ and $B=[2,4,15]$, should the result be $A=[1,2,3,4], B=[9,14,15]$? Also, are the entries integers? Can you use an auxiliary variable for swapping? $\endgroup$ Jan 15 '16 at 16:12
  • $\begingroup$ Yes, The values are integers. You can use with only with constant memory. $\endgroup$
    – Guy Kahlon
    Jan 15 '16 at 16:15
  • 5
    $\begingroup$ This has been answered here. As the commentary indicates, the details are a bit hairy. $\endgroup$ Jan 15 '16 at 17:12
  • 1
    $\begingroup$ Very closely related question. Community, is this a duplicate? $\endgroup$
    – Raphael
    Jan 17 '16 at 16:20
  • $\begingroup$ @Raphael I have tried to create a virtual array with length that equal to the array1's length + array2's length then merge the virtual array with regular QuickSort, But this solution feel very cumbersome. $\endgroup$
    – Guy Kahlon
    Jan 17 '16 at 16:24

Here, great solution, from: http://www.geeksforgeeks.org/merge-two-sorted-arrays-o1-extra-space/

Below is C++ implementation of above algorithm.

// C++ program for implementation of Sieve of Atkin
#include <bits/stdc++.h>
using namespace std;

// Merge ar1[] and ar2[] with O(1) extra space
void merge(int ar1[], int ar2[], int m, int n)
    // Iterate through all elements of ar2[] starting from
    // the last element
    for (int i=n-1; i>=0; i--)
        /* Find the smallest element greater than ar2[i]. Move all
           elements one position ahead till the smallest greater
           element is not found */
        int j, last = ar1[m-1];
        for (j=m-1; j >= 0 && ar1[j] > ar2[i]; j--)
            ar1[j+1] = ar1[j];

        // If there was a greater element
        if (j != m-1)
            ar1[j+1] = ar2[i];
            ar2[i] = last;
  • 2
    $\begingroup$ Code-only answers are not a good fit for this site. What are the ideas? Why does it work? Code should be pseudocode at most. $\endgroup$
    – Raphael
    Jan 17 '16 at 16:17
  • $\begingroup$ @Raphael actually you right I'll update my answer, Thanks for your comment. $\endgroup$
    – Guy Kahlon
    Jan 17 '16 at 16:19
  • $\begingroup$ Also while this solution uses O(1) memory, it takes O(n^2) time, which is quite bad for merging. For instance if you use your merge procedure inside of merge sort algorithm you'll end up with O(n^2) time complexity instead of O(n*log(n)) if you stick with extra memory "vanilla" variant $\endgroup$
    – kravitz
    Jan 26 '20 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.