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

public class SortingDemo
{
    /*
    public static void sort( ArrayList<Integer> arr )
    {
        for( int p = 0; p < arr.size( ); p++ )
        {
            // find index of smallest item in  p..end
            int minIndex = p;
            for( int i = p + 1; i < arr.size( ); i++ )
                if( arr.get( i ) < arr.get( minIndex ) )
                    minIndex = i;
            
            // swap that index with p
            Integer tmp = arr.get( minIndex );
            arr.set( minIndex, arr.get( p ) );
            arr.set( p, tmp );
        }
    }
     */
       
    public static void sort( ArrayList<Integer> arr )
    {
        if( arr.size( ) <= 1 )
            return;
        
        ArrayList<Integer> small = new ArrayList<>( );
        ArrayList<Integer> same  = new ArrayList<>( );
        ArrayList<Integer> large = new ArrayList<>( );
        
        int oneItem = arr.get( arr.size( ) / 2 );
        
        for( int x : arr )
        {
            if( x < oneItem )
                small.add( x );
            else if( x == oneItem )
                same.add( x );
            else if( x > oneItem )
                large.add( x );
        }
        
        sort( small );
        sort( large );
        
        arr.clear( );
        arr.addAll( small );
        arr.addAll( same );
        arr.addAll( large );
    }
       
    public static void main( String [ ] args )
    {
        final int N = 2_000_000;
        Random r = new Random( 1 );
        
        ArrayList<Integer> arr = new ArrayList<>( );
        
        for( int i = 0; i < N; i++ )
            arr.add( r.nextInt( ) );
        
        long start, end;
        
     //   System.out.println( "Before sort: " + arr );
        
        start = System.currentTimeMillis( );
        sort( arr );
        end = System.currentTimeMillis( );
        
    //    System.out.println( "After sort: " + arr );
        System.out.println( "Elapsed time: " + ( end - start ) + " ms." );
    }
    
}