import edu.princeton.cs.algs4.*;

public class SortingCompetition {

	// búum til random fylki:
	private static Double[] randomFylki(int arraySize, long seed) {
    	Double[] x = new Double[arraySize];
    	StdRandom.setSeed(seed);

    	for (int j=0; j<x.length; j++) {
    		x[j] = StdRandom.uniform();
    	}

    	return x;
	}

	// samsetningartími:
    private static double mergeTime(int numTrials, int arraySize, long seed) {
    	double y = 0;
    	StopwatchCPU timi;

        for(int i=0; i<numTrials; i++) {
        	Double[] x = randomFylki(arraySize, seed);

        	timi = new StopwatchCPU(); // búum til skeiðklukku

	    	Merge.sort(x);

	    	y += timi.elapsedTime(); // tíminn frá því að skeiðklukkan varð til
        }

        y /= numTrials; // meðaltal
    	return y;
    }

    // innsetningartími:
    private static double insertionTime(int numTrials, int arraySize, long seed) {
    	double y = 0;
    	StopwatchCPU timi;

        for(int i=0; i<numTrials; i++) {
        	Double[] x = randomFylki(arraySize, seed);

        	timi = new StopwatchCPU(); // búum til skeiðklukku

	    	Insertion.sort(x);

	    	y += timi.elapsedTime(); // tíminn frá því að skeiðklukkan varð til
        }

        y /= numTrials; // meðaltal
    	return y;
    }

    public static void main(String[] args) {

        int maxN = 1000; // Við gefumst upp eftir 1000 stök
        int numTrials = 50000; // Fjöldi mælinga fyrir hverja stærð fylkis, hér mjög stórt
        long seed = 203; // Fastur grunnur fyrir slembitölugjafann
        int n = 10; // Byrjum að skoða fylki af þessari stærð

        double insertionTime = 0;
        double mergeTime = Long.MAX_VALUE;

        while (insertionTime < mergeTime && n < maxN) {
            insertionTime = insertionTime(numTrials, n, seed);
            mergeTime = mergeTime(numTrials, n, seed);
            n++;

            //System.out.println("n: " + n + ", insertion: " + insertionTime + ", merge: " + mergeTime + ", ");
        }
        StdOut.println(n);
    }

}