class PrimitiveArrays {

    public static int[] union( int[] lhs, int[] rhs )
    {
        if ( lhs == null || rhs == null )
        {
            return lhs == null ? rhs : lhs;
        }

        assert isSortedSet( lhs ) && isSortedSet( rhs );
        if ( lhs.length < rhs.length )
        {
            return union( rhs, lhs );
        }
        int[] merged = null;
        int m = 0;
        int l = 0;
        for ( int r = 0; l <= lhs.length && r < rhs.length; )
        {
            while ( l < lhs.length && lhs[l] < rhs[r] )
            {
                if ( merged != null )
                {
                    merged[m++] = lhs[l];
                }
                l++;
            }
            if ( l == lhs.length )
            {
                if ( merged == null )
                {
                    merged = Arrays.copyOf( lhs, lhs.length + rhs.length - r );
                    m = l;
                }
                System.arraycopy( rhs, r, merged, m, rhs.length - r );
                m += rhs.length - r;
                break;
            }
            if ( lhs[l] > rhs[r] )
            {
                if ( merged == null )
                {
                    merged = Arrays.copyOf( lhs, lhs.length + rhs.length - r );
                    m = l;
                }
                merged[m++] = rhs[r++];
            }
            else // i.e. ( lhs[l] == rhs[r] )
            {
                if ( merged != null )
                {
                    merged[m++] = lhs[l];
                }
                l++;
                r++;
            }
        }
        if ( merged == null )
        {
            return lhs;
        }
        if ( l < lhs.length ) // get tail of lhs
        {
            System.arraycopy( lhs, l, merged, m, lhs.length - l );
            m += lhs.length - l;
        }
        if ( m < merged.length ) // truncate extra elements
        {
            merged = Arrays.copyOf( merged, m );
        }
        return merged;
    }

    private  PrimitiveArrays();

}