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.