Merging two arrays without using extra space

Question

I have 2 sorted arrays, a1 and a2, of lengths l1 and l2, respectively. The array a2 has empty space at the end of length l1, so it can hold all of the elements of a1 in addition to its own elements. Now, I want to merge a1 into a2 so that a2 will contain all the elements of a1 and a2 in sorted order. Ideally this should use O(1) auxiliary storage space. I have the following cod,e but something is going wrong:

 public static int[] merge(int []a1,int a2[],int l1, int l2){

         System.out.println("l1 =" +l1 + " l2=" +l2);
         int es = l2-l1;
         int fs = l2-es;

         System.out.println("es= " +es);
         System.out.println("fs = " + fs);
         int j=0;

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

             if(j<fs){
                // System.out.println("i= " + i + "a1[i]=" + a1[i]);
                // System.out.println("j= " + j + "a2[j]=" + a2[j]);
                 if(a1[i]<a2[j]){
                     add(a2,j,a1[i],l2);
                     //i++;
                     fs++;
                 }
             }else{
                 System.out.println("***");
                 a2[j]=a1[i];
             }

             j++;
         }

         return a2;
     }


    public static void add(int []a,int p,int key,int l){

        for(int i=l-1;i>p;i--){
              a[i]= a[i-1];
        }
        a[p]= key;
    }

Does anyone have any ideas on how to fix this? I used following data to run the code:

int a1[]= new int[]{-1,0,7,8};
int a2[]= new int[7];
a2[0]=1;
a2[1]=3;
a2[2]=9;

Output is

l1 =4 l2=7
es= 3
fs = 4
-1
0
1
3
9
0
0

Answer 1

It's difficult to tell what your code does, but it seems to have suboptimal (O(n^2)) complexity: there's a second loop inside add method.
Also, note that fs is always equal to l1.

But there's much simpler method: from the back. If you think about it, there's always enough space.

Something like this

int i = l1 - 1;
int j = l2 - 1;
int result_pos = l1 + l2 - 1;
while (i >= 0 || j >= 0) {
    if (a1[i] >= a2[j]) {
        a2[result_pos--] = a1[i--];
    } else {
        a2[result_pos--] = a2[j--];
    }
}

PS You'll need to add handling for the case when one of i and j is negative in the loop. Obviously, in this case another element should be copied.

edit
Later can be done with this condition

if (j < 0 || (i >= 0 && a1[i] >= a2[j])) {

instead of

if (a1[i] >= a2[j]) {

Answer 2

If the elements in a1 and a2 are sorted then you'd have something like this:

a1 : [-1] [0] [7] [8]
a2 : [1] [3] [9] [] [] [] []

So in code you can do this:

int a1i = 0; // pointer to the ith element in the array a1
int tmp = 0;
int i = 0;
for(i = 0; i < a1.length; i++) {
    if(a2[i] > a1[a1i]) {
        tmp = a2[i];
        a2[i] = a1[a1i];
        a1[a1i] = tmp;
        Arrays.sort(a1); // This might take more memory though...
    } else {
        a1i++;
    }
}
a1i = 0;
for(i; i < a2.length; i++) {
    a2[i] = a1[a1i];
    a1i++;
}

This would work out to:

a1 : [-1] [0] [7] [8]
      ^
a2 : [1] [3] [9] [] [] [] []
      ^
SWAP

a1 : [1] [0] [7] [8]
      ^
a2 : [-1] [3] [9] [] [] [] []
           ^
SORT

a1 : [0] [1] [7] [8]
      ^
a2 : [-1] [3] [9] [] [] [] []
           ^
SWAP

a1 : [3] [1] [7] [8]
      ^
a2 : [-1] [0] [9] [] [] [] []
               ^
SORT

a1 : [1] [3] [7] [8]
      ^
a2 : [-1] [0] [9] [] [] [] []
               ^
SWAP

a1 : [9] [3] [7] [8]
      ^
a2 : [-1] [0] [1] [] [] [] []
                  ^
SORT

a1 : [3] [7] [8] [9]
      ^
a2 : [-1] [0] [1] [] [] [] []
                  ^
COPY

a1 : [3] [7] [8] [9]
          ^
a2 : [-1] [0] [1] [3] [] [] []
                   ^
COPY

a1 : [3] [7] [8] [9]
              ^
a2 : [-1] [0] [1] [3] [7] [] []
                       ^
COPY

a1 : [3] [7] [8] [9]
                  ^
a2 : [-1] [0] [1] [3] [7] [8] []
                           ^
COPY

a1 : [3] [7] [8] [9]
                  ^
a2 : [-1] [0] [1] [3] [7] [8] [9]
                               ^
END

Answer 3

First, shift the elements of a1 to the back of a1. Second merge a1 and a2 starting the front of a1 (i.e., write the minimum of the two elements being compared to the current index in a1, where the current index starts at 0 and ranges up to a1.length + a2.length - 1). This will prevent you from overwriting any elements of a1.

Answer 4

I'd start merging from the end.

At the last element, put max(lastOf(a1), lastOf(f2)). Continue to bite off one element at a time from the rest of either array, until one of these is exhausted. Put the rest of the remaining array to the start (may me a no-op).

Answer 5

There are many good answers. I just wanted to add something (the comments are already so buried):

This is just the merging phase of a merge-sort or similar such as a k-way sort. Just use an in-place merge routine. Either the "smaller array" or the "empty space" can be used to store values in the "larger array" which are not currently in sort-order.

It's okay to borrow bits and pieces of different algorithms :-)

Answer 6

The better way to solve the question is used to Insertion sort for merging two sorted arrays in O(1) auxiliary space.

/* as we have to merge the 2 sorted arrays in array2. we begin from the end of array2 and insert the array element at its correct position acc. to insertion sort*/

public static int[] merge(int []a1,int a2[],int l1, int l2){

     int len2=l2-l1;
      for(int i=l1-1;i>=0;i--){
        int j=len2-1;

          for(;j>=0 && j+1<l2 && a2[j]>a[i];j--){
             a2[j+1]=a2[j];
           }
          a2[j+1]=a1[i];
            len2++;
         }
}

Answer 7

Merge Two Sorted Array Without Using Extra Memory

#include<iostream>
using namespace std ;
const int N = 100 ;
int a[N] , b[N] , n , m , len , L ;
int main() {
    cin >> n ;
    for( int i = 0 ; i < n ; i++ ) cin >> a[i] ;
    cin >> m ;
    for( int i = 0 ; i < m ; i++ ) cin >> b[i] ;
    len = n + m - 1 ;
    L = n + m ;
    n--  , m-- ;
    while( len >= 0 ) {
        if( m < 0 ) a[len] = a[n--];
        else if( n < 0 ) a[len] = b[m--];
        else if( a[n] > b[m] ) a[len] = a[n--];
        else a[len] = b[m--];
        len--;
    }
    for( int i = 0 ; i < L ; i++ ) cout << a[i] << " " ;
}

Answer 8

This is nothing but merge phase of merge sort,

1. copy all the elements of a2 (1,2,3,4) at the end of a1 (5,6,7,8), now a1 will contain (4,5,6,7,8,1,2,3,4)
2. Now invoke the merge algorithm below inPlaceMerge(collection, 0<low>,3<mid>,7<high>);

here is the algorithm in Java,

public static <T extends Comparable<? super T>>  void inPlaceMerge(T[] collection, int low, int mid, int high) {
    int left = low;
    int right = mid + 1;

    if(collection[mid].equals(collection[right])) {
        return ;//Skip the merge if required
    }
    while (left <= mid && right <= high) {          
        // Select from left:  no change, just advance left
        if (collection[left].compareTo(collection[right]) <= 0) {
            left ++;
        } else { // Select from right:  rotate [left..right] and correct
            T tmp = collection[right]; // Will move to [left]
            rotateRight(collection, left, right - left);
            collection[left] = tmp;
            // EVERYTHING has moved up by one
            left ++; right ++; mid ++;
        }
    }       
}

private static <T extends Comparable<? super T>> void rotateRight(T[] collection, int left, int numberOfElements) {
    System.arraycopy(collection, left, collection, left+1, numberOfElements);       
}

Here is the unit test

@Test
public void inPlaceMergeFirstTest() {
    Integer[] collection = new Integer[]{5,6,7,8,1,2,3,4};
    ArrayUtils.<Integer>inPlaceMerge(collection, 0,3,7);
    Integer[] result = new Integer[]{1,2,3,4,5,6,7,8};
    assertThat(collection, equalTo(result));
}

Answer 9

Why bother writing your own code? If a2 has enough empty space to hold the elements of a1, just copy tha elements from a1 into a2 (using arraycopy) and then use Arrays.sort(). That would give you O(n*log(n)) whereas your simple approach seems to be O(n*n) anyway.

(However the merge could be done in O(n).)

Answer 10

I assume you have no restriction on time complexity of your algorithm. My suggestion is to append the values of a1 to a2 and apply any O(nlogn) sorting algorithm like quicksort. However if you'd like to do the merging, i think this code helps you:

public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a1[]= new int[]{-1,0,7,8};
        int a2[]= new int[7];
        a2[0]=1;
        a2[1]=3;
        a2[2]=9;
        merge(a1, a2, 3);
    }

    private static void merge(int[] a1, int[] a2, int lastPos) {
        for ( int i = 0; i < a1.length; i++)
        {
            for ( int j = 0; j < a2.length; j++)
                if ( a1[i] < a2[j] )
                {
                    add(a1[i], a2, j, lastPos);
                    lastPos++;
                    break; //since a2 is also sorted
                }
        }
    }

    private static void add(int val, int[] a2, int j, int lastPos) {
        for ( int i = lastPos; i > j; i--)
            a2[i] = a2[i-1];
        a2[j] = val;
    }

Answer 11

/or simply you can do this->/

public static int[] merge(int []a1,int a2[],int l1, int l2){
     int j=0;
     for(int i=l2-l1;i<l2;i++)
     {
            a2[i]=a1[j];
              j++;
      }
      Arrays.sort(a2);
      return a2;

 }

Answer 12

A quick approach is by using a Heap. Check this out:

public static void merge(long arr1[], long arr2[], int n, int m) 
    {
        PriorityQueue<Long> pq=new PriorityQueue<>();
        for(int i=0; i<n; i++){
            pq.add(arr1[i]);
        }
        for(int j=0; j<m; j++){
            pq.add(arr2[j]);
        }
        for(int k=0; k<n; k++){
            arr1[k]=pq.poll();
        }
        for(int l=0; l<m; l++){
            arr2[l]=pq.poll();
        }
    }

Answer 13

have you tried System.arrayCopy? Something like :

...
System.arraycopy(a2, 0, a2, a1.length, a2.length);
System.arraycopy(a1, 0, a1, 0, a1.length);
...

Should do the trick while not wasting time (arraycopy is optimized for these use cases).