import java.util.*;
public class Algoritmi{
    public static void main(String[] args){
        Scanner tastiera=new Scanner(System.in);

        System.out.println("inserisci la lunghezza del vettore di interi");
        int lunghezza=tastiera.nextInt();

        int i=0;
        int j=lunghezza-1;

        int[] v=new int[lunghezza];
        System.out.println("inserisci i valori del vettore");
        for(int z=0; z<lunghezza;z++)
            v[z]=tastiera.nextInt();
        stampaVettori(v);

        char input=stampaMenu();
        switch(input){
            case '1':
                mergeSort(v,i,j);
                stampaVettori(v);
            break;
            default:
            System.exit(0);
            break;
        }

    }







//METODI
    //stampa array

    public static void stampaVettori(int[] v){
        System.out.print("[");
        for(int h=0; h<v.length;h++)
            System.out.print("_"+v[h]);
        System.out.print("]");
    }
    //stampa menu
    public static char stampaMenu(){
        String input;
        Scanner tastiera=new Scanner(System.in);

        System.out.println("\nPremi 1 se vuoi merge sort");
        //INSERIRO' ALTRE OPZIONI
        System.out.println("Premi qualunque altro tasto per uscire");

        input=tastiera.nextLine();
        return input.charAt(0);
    }

    //Merge Sort                            //MI DA QUALCHE ERRORE

    public static void mergeSort(int[] v, int i, int j){
        int q;
        if(i<j){
            q=(i+j)/2;
            //System.out.println("\n\n i: "+i+" j: "+j+" q: "+q);       //DEBUG
            mergeSort(v,i,q);
            mergeSort(v,q+1,j);
            merge(v,i,q,j);
        }
    }
    public static void merge(int[] v, int i, int q, int j){
        int n1=q-i+1;                       //lunghezza di v[i,q]
        int n2=j-q;                         //lunghezza di v[q+1,j]

        int[] left=new int[n1+1];           //vettori di appoggio
        int[] right=new int[n2+1];


        //ricopio in left e right
        int l=0;
        int r=0;
        int a;
        for(l=0;l<n1;l++){
            left[l]=v[l+i];
        }
        for(r=0;r<n2;r++){
            right[r]=v[q+1+r];
        }

        left[n1]=999999;                    //valori sentinella
        right[n2]=999999;

        /*//debug
        System.out.println("\n\nleft");
        stampaVettori(left);
        System.out.println("\n\nright");
        stampaVettori(right);
        //fine debug*/

        l=0;                                //inizializzo gli indici
        r=0;

        for(a=i; (a<left.length)&&(a<right.length); a++){               //inizio ad ordinare
            if((left[l]==999999)&&(right[r]==999999)){
                System.out.println("finito");
                break;
            }

            if((left[l]==999999)&&(right[r]!=999999))
                left[l]=right[r]+1;

            if((left[l]!=999999)&&(right[r]==999999))
                right[r]=left[l]+1;

            if(left[l]<=right[r]){
                v[a]=left[l];
                l++;
            }
            else{
                v[a]=right[r];
                r++;
            }
        }
    }
}