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

public class Day06
{
    public static int f( int x )
    {
        if( x == 0 )
            return 0;
        else if( x > 0 )
            return f( x - 1 ) + 2 * x - 1;
        else
            return f( -x );
    }

    public static int g( int n )
    {
        if( n == 0 || n == 1 )
            return 1;

        return g( n / 2 ) + 1;
    }

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

            // find index of smallest item in [i..]
            for( int j = i + 1; j < arr.size( ); j++ )
                if( arr.get( j ) < arr.get( minIndex ) )
                    minIndex = j;

            int tmp = arr.get( i );
            arr.set( i, arr.get( minIndex ) );
            arr.set( minIndex, tmp );
        }
    }
     */
    public static void sort( ArrayList<Integer> arr )
    {
        if( arr.size( ) <= 1 )
            return;

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

        int randomItem = arr.get( arr.size( ) / 2 );  // pick the middle for now

        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 main( String [ ] args )
    {
        /*
        for( int i = 0; i <= 16; i++ )
            System.out.println( "g(" + i + ")=" + g( i ) );
         */

        ArrayList<Integer> arr = new ArrayList<Integer>( );
        Random r = new Random( 1 );
        final int N = 2000000;

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

        //System.out.println( arr );
        long startTime = System.currentTimeMillis( );
        sort( arr );
        long endTime = System.currentTimeMillis( );

        System.out.println( "Elapsed time is " + (endTime - startTime) + "ms" );
        //System.out.println( arr );

    }

}