Thursday 21 August 2014

merge one array of size n into another one of size m+n

Lets say Array 'b' has 'n' number of Elements in sorted order and 'a' has 'm+n' elements, where first 'm' elements are in sorted order and next 'n' positions are empty. Merge arrays 'a' and 'b' and store the result to array 'a'.

public class Merge {
    
    static void merge(int a[], int b[]){
        int aLen = a.length;
        int bLen = b.length;
        
        int aEnd = aLen-bLen;
        
        aLen--;
        bLen--;
        
        /* Represents Elements end location of array a */
        aEnd--;
        
        while(aEnd > -1 && bLen > -1){
            if(a[aEnd] > b[bLen]){
                a[aLen] = a[aEnd];
                aEnd--;
                aLen--;
            }
            else{
                a[aLen] = b[bLen];
                bLen--;
                aLen--;
            }
        }
        
      if(aEnd == -1){
            for(int i=bLen; i>-1; i--){
                a[aLen] = b[i];
                aLen--;
            }
        }
        if(bLen == -1){
            for(int i=aEnd; i>-1; i--){
                a[aLen] = a[i];
                aLen--;
            }
        }
    }
    public static void main(String args[]){
        int a[] = {1, 6, 11, 12, -1, -1, -1};
        int b[] = {5, 8, 10};
        
        merge(a,b);
        
        for(int i=0; i<a.length; i++){
            System.out.print(a[i] +" ");
        }
    }
}

Output
1 5 6 8 10 11 12




Prevoius                                                 Next                                                 Home

No comments:

Post a Comment