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

public class Recursion 
{
    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 qsort( 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 );

        qsort( smaller );
        qsort( larger );

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

    public static void main( String [ ] args )
    {
        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( ) );

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

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

    }

}