Two way merge

ISC Computer Science 2014

This problem of merging two sorted integer arrays into a third integer array such that the resultant is also sorted is popularly known as ‘Two way merge‘ in computing. Note that arrays are not to be copied into the third array and then sorted.

Question 8

A class Mixer has been defined to merge two sorted integer arrays in ascending order. Some of the members of the class are given below:

Class name: Mixer

Data members/instance variables:

int arr[]            : to store the elements of an array
int n                : to store the size of the array

Member functions:

Mixer( int nn)      : constructor to assign n = nn
void accept()       : to accept the elements of the array in ascending 
                      order without any duplicates
Mixer mix( Mixer A) : to merge the current object array elements with 
                      the parameterized array elements and return the 
                      resultant object
void display()      : to display the elements of the array

Specify the class Mixer, giving details of the constructor(int), void accept(), Mixer mix(Mixer) and void display(). Define the main function to create an object and call the function accordingly to enable the task.


The Java program for the Mixer class (Two way merge) is as follows:

import java.util.*;
class Mixer{
    private int arr[ ];
    private int n;
    public Mixer( int nn ){
        n = nn;
        arr = new int[ n ];
    }
    public void accept(){
        Scanner sc = new Scanner( System.in );
        for( int i=0; i< n; i++ ){
            arr[ i ] = sc.nextInt();
        }
    }
    public Mixer mix( Mixer A ){
        Mixer ans = new Mixer( this.arr.length + A.arr.length );
        int p1, p2, p3;
        p1 = p2 = p3 = 0;
        while( p1 < this.arr.length && p2 < A.arr.length ){
            if( this.arr[ p1 ] < A.arr[ p2 ] ){
                ans.arr[ p3++ ] = this.arr[ p1++ ];
            }else{
                ans.arr[ p3++ ] = A.arr[ p2++ ];
            }
        }
        if( p1 < this.arr.length ){
            for( int i = p1 ; p1 < this.arr.length; i++ ){
                ans.arr[ p3++ ] = this.arr[ p1++ ];
            }
        }else if( p2 < A.arr.length ){
            for( int i = p2 ; p2 < A.arr.length; i++ ){
                ans.arr[ p3++ ] = A.arr[ p2++ ];
            }
        }
        return ans;
    }
    public void display(){
        for( int i=0; i < arr.length; i++ ){
            System.out.print( arr[i] + " " );
        }
        System.out.println();
    }
    public static void main( String args[] ){
        Mixer obj1 = new Mixer(5);
        Mixer obj2 = new Mixer(3);

        obj1.accept();
        obj2.accept();

        Mixer obj3 = obj1.mix( obj2 );
        obj3.display();
    }
}

Sample input/output is as follows:

1 2 3 4 5
2 3 5
1 2 2 3 3 4 5 5

Notice that even though there are three loops in the mix function, the complexity is still O(N) because the last two loops are mutually exclusive, that is, only one of them would execute. Feel free to use the comment box below in case of any queries.

2 thoughts on “Two way merge

  1. Hifjur Rehman Siddiqui

    Loved ur blog very much Sir………. 🙂
    Saw all of your programs.
    Liked it very much……..
    So much well and good explained that nothing else is needed.
    The programs are self-explanatory.
    The most important is that within so short duration of time you did it.
    I think it should be published and your book instead of other authors
    should be preferred.
    -Yours Faithfully

    Reply
    1. Vinay Singh Post author

      Thank you for the appreciation. I would proceed with idea of getting it published once the number of posts are substantial. Also, the text would require extensive changes because books are different from blog posts and there are no hyperlinks in books pointing to external resources!

      Reply

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.