import java.util.*;   // for Random
public class MySort {
	private static final Random RAND = new Random(42);   // random number generator

 	public static void main(String[] args) throws Throwable {
		
		int RUNS   =  11;   // On double 11 fois la taille
		int maxTrial=10;   // on effectue 10 test par taille
		int cpuMax=8;      // on teste avec 1,2,4,8  thread.cpu
		
		for (int cpuNum=1; cpuNum<= cpuMax; cpuNum*=2)
		    {
			int mTaille = 4096;   // Taille de base
			System.out.printf("Stats for %d cores\n", cpuNum);
			for (int i = 1; i <= RUNS; i++) {
			    long totalTime=0;
			    for(int cTry=0; cTry< maxTrial; cTry++)
				{
				    int[] a = createRandomArray(mTaille);
				    long begin = System.currentTimeMillis();
				    mSort(a, cpuNum, "");
				    long end= System.currentTimeMillis();
				    totalTime+= end -begin ;
				}
			System.out.printf("%10d elements  =>  %6d ms \n", mTaille, totalTime/maxTrial);
			mTaille *= 2;   // double size of array for next time
			}
		    }
	}

    public static void mSort(int[] a, int AvailCPU, String branch) throws InterruptedException  {
	       if (a.length >= 2) {
			// Decoupe le tableau en 2 left and right
			int[] left  = Arrays.copyOfRange(a, 0, a.length / 2);
			int[] right = Arrays.copyOfRange(a, a.length / 2, a.length);

			// Only one cpu we perform a recursive but sequential  sort
			if (AvailCPU <= 1)
			    {
				mSort(left, AvailCPU, branch+"0");
				mSort(right, AvailCPU, branch+"1");
			    }
			// If 2++ Cpu we create a thread to sort left and right
			else
			    {
				Thread lThread = new Thread(new Sorter(left,  AvailCPU / 2, branch+"0" ));
				Thread rThread = new Thread(new Sorter(right, AvailCPU / 2, branch+"1" ));
				lThread.start();
				rThread.start();
				lThread.join();
				rThread.join();
			    } 
			// fusionne les tableaux left et right
			// La fusion est sequentielle 
			fusion(left, right, a);
		}
    }
	

	public static void fusion(int[] left, int[] right, int[] a) {
		int leftI = 0;
		int rightI = 0;
		for (int i = 0; i < a.length; i++) {
			if (rightI >= right.length || (leftI < left.length && left[leftI] < right[rightI])) {
				a[i] = left[leftI];
				leftI++;
			} else {
				a[i] = right[rightI];
				rightI++;
			}
		}
	}
	
	
	// Swaps the values at the two given indexes in the given array.
	public static final void exchange(int[] a, int i, int j) {
		if (i != j) {
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}
	
// Melange un tableau
	public static void shuffle(int[] a) {
		for (int i = 0; i < a.length; i++) {
			int randomIndex = (int) (Math.random() * a.length - i);
			exchange(a, i, i + randomIndex);
		}
	}
	
	// Crée un tableau aléatoire
	public static int[] createRandomArray(int length) {
		int[] a = new int[length];
		for (int i = 0; i < a.length; i++) {
			a[i] = RAND.nextInt(1000000);
		}
		return a;
	}
}