import java.util.ArrayList;
import java.util.Random;

interface NewFunction
{
    double eval( double x );
}
class X_PLUS_7 implements NewFunction
{
    public double eval( double x )
    {
        return x + 7;
    }
}

class X_SQUARED implements NewFunction
{
    public double eval( double x )
    {
        return x * x - 10 * x + 5;
    }
}

class X_CUBED implements NewFunction
{
    public double eval( double x )
    {
        return x * x * x - 8;
    }
}

public class Day17
{
    // Given f(x), with f(a)<0 and f(b)>0, find f(c)==0
    public static double solve( NewFunction f, double a, double b )
    {
        if( Math.abs( b - a ) < 0.000000000001 ) // converged
            return a;

        double c = ( a + b ) /2;

        double fc = f.eval( c );  // f(c)

        if( fc == 0 )
            return 0;

        if( fc < 0 )   // the answer lies between c (neg) and b (pos)
            return solve( f, c, b );
        else           // the answer lies between a (neg) and c (pos)
            return solve( f, a, c );
    }

    /*
    public static void main( String [ ] args )
    {
        System.out.println( solve( new X_PLUS_7( ), -100000, +1000000 ) );
        System.out.println( solve( new X_SQUARED( ), 5, 100 ) );
        System.out.println( solve( new X_CUBED( ), 0, 1000 ) );
    }
     * */

    public static int f( int x )
    {
        if( x == 0 )   // BASE CASE
            return 0;
        else 
            return f( x - 1 ) + 2 * x - 1;
    }

    public static void sort( ArrayList<Integer> arr )
    {
        if( arr.size( ) <= 1 )  // BASE CASE
            return;

        ArrayList<Integer> smaller = new ArrayList<Integer>( );
        ArrayList<Integer> same    = new ArrayList<Integer>( );
        ArrayList<Integer> larger  = new ArrayList<Integer>( );

        Integer randomItem = arr.get( arr.size( ) / 2 );

        for( Integer x : arr )
            if( x < randomItem )
                smaller.add( x );
            else if( x > randomItem )
                larger.add( x );
            else
                same.add( x );

        sort( smaller );
        sort( larger );

        arr.clear( );
        arr.addAll( smaller );
        arr.addAll( same );
        arr.addAll( larger );
    }

    /*
    public static void sort( ArrayList<Integer> arr )
    {
        for( int p = 0; p < arr.size( ); p++ )
        {
            int minIndex = p;

            for( int j = p + 1; j < arr.size( ); j++ )
                if( arr.get( j ) < arr.get( minIndex ) )
                    minIndex = j;

            // minIndex has smallest item from p onwards
            // swap arr[p] and arr[minIndex]
            Integer tmp = arr.get( p );
            arr.set( p, arr.get( minIndex ) );
            arr.set( minIndex, tmp );
        }
    }
     * */

    public static void main( String [ ] args )
    {
        /*
        for( int i = 0; i < 10; i++ )
            System.out.println( "f(" + i +")=" + " " + f( i ) );
        */
        
        Random r = new Random( );
        ArrayList<Integer> arr = new ArrayList<Integer>( );
        final int N = 1000000;

        for( int i = 0; i < N; i++ )
            arr.add( r.nextInt( 100000 ) );

       // System.out.println( arr );
        long start = System.currentTimeMillis( );
        sort( arr );
        long end = System.currentTimeMillis( );
        //System.out.println( arr );

        System.out.println( "Elapsed time: " + ( end - start ) + "millisec" );
    }
}