import java.util.Scanner;

public class Main {

	public static int sommaElemArray (int[] a, int inizio, int fine){
		if (inizio==fine) {
			return a[inizio];
		}
		int medio = (inizio+fine)/2;
		int sommaSx = sommaElemArray (a, inizio, medio);
		int sommaDx = sommaElemArray (a, medio+1, fine);
		return sommaSx+sommaDx;
	}
	
	
	public static int sommaElemArray (int[] a){
		return sommaElemArray (a,0,a.length-1);		
	}
	
	public static void testSommaElemArray (){
		int [] a = leggiArray();
		System.out.println("La somma degli elementi dell'array è " 
		                    + sommaElemArray(a));
		
	}
	
	
	public static void stampaArray (int[] a){
		System.out.print ("{");
		for (int i=0; i<a.length; i++) {
			System.out.print (a[i]);
			if (i<a.length-1) {
				System.out.print ( ", ");
			}
		}
		System.out.println ("}");
	}

	
	public static int[] leggiArray (){
		Scanner s = new Scanner(System.in);
		int n;
		do{
			System.out.print ("Inserisci la lunghezza dell'array: ");
			n=s.nextInt();
			s.nextLine();
		} while (n<=0);
		int[] ris = new int[n];
		for (int i=0; i<n; i++){
			System.out.print ("Inserisci l'elemento in posizione " + (i+1) +": ");
			ris[i]=s.nextInt();
			s.nextLine();
		}
		return ris;
	}
	
	
	public static boolean ricercaBinaria (int[] a, int n, int inizio, int fine){
		if (inizio>fine) {
			return false;
		}
		int medio = (inizio+fine)/2;
		if (a[medio]==n){
			return true;
		}
		if (a[medio]>n){
			return ricercaBinaria (a, n, inizio, medio-1);
		} else {
			return ricercaBinaria (a, n, medio+1, fine);
		}
	}
	
	public static boolean ricercaBinaria (int[] a, int n){
		return ricercaBinaria (a, n, 0, a.length-1);		
	}
	
	public static void testRicercaBinaria(){
		Scanner s = new Scanner(System.in);
		int[] a = leggiArray();
		while (true){
			System.out.print ("Inserisci il numero da cercare: ");
			int n=s.nextInt();
			s.nextLine();
			if (ricercaBinaria (a,n)) {
				System.out.println ("L'intero " + n + " è presente nell'array");
			} else {
				System.out.println ("L'intero " + n + " non è presente nell'array");
			}
		}		
	}
	
	public static int[] ruotaArray (int[] a, int n){
		int shift = n % a.length;
		if (shift<0) {
			shift +=a.length;
		}
		int [] ris = new int [a.length];
		for (int i=0; i<a.length; i++){
			ris[i]=a[(i+shift)%a.length];
		}
		return ris;
	}
	
	public static void testRuotaArray(){
		Scanner s = new Scanner(System.in);
		int[] a = leggiArray();
		while (true){
			System.out.print ("Inserisci il valore della rotazione: ");
			int n=s.nextInt();
			s.nextLine();
			int [] b = ruotaArray(a,n);
			stampaArray(b);
		}		
	}
	
	public static void selectionSort (int[] a){
		for (int i=0; i<a.length-1; i++){
			int posMin=i;
			for (int j=i+1; j<a.length; j++){
				if (a[j]<a[posMin]) {
					posMin=j;
				}
			}
			int temp=a[i];
			a[i]=a[posMin];
			a[posMin]=temp;
		}
	}
	
	public static void testSorting(){
		//int[] a = leggiArray();
		Scanner s = new Scanner(System.in);
		System.out.print ("Inserisci la lunghezza dell'array: ");
		int n=s.nextInt();
		s.nextLine();
		int[]a = generaArray(n, 1000000);
		int[]b = copiaArray(a);
				
		System.out.println ("Inizio merge-Sort");
		//stampaArray(a);
		mergeSort(a);
		//stampaArray(a);
		System.out.println ("Fine merge-Sort");
		
		System.out.println ("Inizio selection-Sort");
		//stampaArray(b);
		selectionSort(b);
		//stampaArray(b);
		System.out.println ("Fine selection-Sort");
				
	}
	
	public static void mergeSort (int [] a){
		int [] aux = new int [a.length];
		mergeSort (a, aux, 0, a.length-1);
	}
	
	public static void mergeSort (int[] a, int[] aux, int inizio, int fine){
		if (inizio != fine) {
			int m = (inizio+fine)/2;
			mergeSort (a, aux, inizio, m);
			mergeSort (a, aux, m+1, fine);
			merge (a, aux, inizio, m+1, fine);			
		}
	}
	
	public static void merge (int[]a, int[] aux, 
			                    int inizioSx, int inizioDx, int fineDx){
		int posMinSx = inizioSx;
		int posMinDx = inizioDx;
		
		for (int i=inizioSx; i<=fineDx; i++){
			if (posMinSx>=inizioDx || (posMinDx<=fineDx && a[posMinDx]<a[posMinSx])) {
				aux[i]=a[posMinDx];
				posMinDx++;
			} else {
				aux[i]=a[posMinSx];
				posMinSx++;
			}
		}
		
		for (int i=inizioSx; i<=fineDx; i++){
			a[i]=aux[i];
		}
	}
	
	public static int[] generaArray (int n, int max){
		int [] a = new int [n];
		for (int i=0; i<a.length; i++){
			a[i]= (int) (Math.random() * max) ;
		}
		return a;		
	}
	
	public static int[] copiaArray (int[] a){
		int[] copia = new int [a.length];
		for (int i=0;i<a.length;i++){
			copia[i]=a[i];
		}
		return copia;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//testRicercaBinaria ();
		//testSommaElemArray();
		//testRuotaArray();
		testSorting();
		
		
	}

}