import javax.swing.JOptionPane;

/*
  Implementa l'ordinamento per fusione
*/		
public class MergeSort
{
	static void stampaVettore(int[] v)
	{
		for(int i=0; i<v.length; i++)
		{
			System.out.println(v[i]);
		}
		return;
	}
		

	static int[] leggiVettore()
	{
		int n = Integer.parseInt(JOptionPane.showInputDialog("Quanti elementi?"));

		int[] vett=new int[n];
		for(int i=0; i<n; i++)
		{
			vett[i] = Integer.parseInt(JOptionPane.showInputDialog("Digita intero in posiz. "+i));
		}
		return vett;
	}
		

	static void riempiVettoreRandom(int[] vett, int valoreMassimo)
	{
		for(int i=0; i<vett.length; i++)
		{
			vett[i] = (int) (Math.random() * valoreMassimo);
		}
	}

		

/*
	Fonde due subintervalli adiacenti di un array
	@param a l'array con le voci da fondere
	@param from l'indice del primo elemento del primo intervallo
	@param mid l'indice dell'ultimo elemento del primo intervallo
	@param to l'indice dell'ultimo elemento del secondo intervallo 
*/
	static void merge(int[] a, 
		int from, int mid, int to)
	{	int n = to - from + 1;
		// dimensione dell'intervallo da fondere

		// fonde entrambe le metà in un array temporaneo b
		int[] b = new int[n];

		int i1 = from;
			// elemento successivo da considerare nel primo intervallo
		int i2 = mid + 1;
			// elemento successivo da considerare nel secondo intervallo
		int j = 0; 
			// successiva posizione aperta in b

		// fin tanto che né i1 né i2 supera la fine, sposta
		// l'elemento più piccolo in b
		while (i1 <= mid && i2 <= to)
		{	if (a[i1] < a[i2])
			{	b[j] = a[i1];
				i1++;
			}
			else
			{	b[j] = a[i2];
				i2++;
			}
			j++;
		}

		// si osservi che viene eseguito uno solo dei due cicli while 
		// che seguono

		// copia eventuali voci rimanenti della prima metà
		while (i1 <= mid)
		{	b[j] = a[i1];
			i1++;
			j++;
		}

		// copia eventuali voci rimanenti della seconda metà
		while (i2 <= to)
		{	b[j] = a[i2];
			i2++;
			j++;
		}

		// ricopia dall'array temporaneo
		for (j = 0; j < n; j++)
			a[from + j] = b[j];
	}



	/*
		Ordina un intervallo di un array, usando l'algoritmo 
		dell'ordinamento per fusione.
		@param a l'array da ordinare
		@param from il primo indice dell'intervallo da ordinare
		@param to l'ultimo indice dell'intervallo da ordinare
	*/
	static void mergeSort(int[] a, int from, int to)
	{	if (from == to) return;
		int mid = (from + to) / 2;
		 // ordina la prima e la seconda metà
		mergeSort(a, from, mid);
		mergeSort(a, mid + 1, to);
		merge(a, from, mid, to);
	}



	/*
		Ordina un array, usando l'algoritmo
.		dell'ordinamento per fusione.
		@param a l'array da ordinare
	*/
	static void sort(int[] a)
	{	mergeSort(a, 0, a.length - 1);
	}



	public static void main(String[] args)
	{
//		int[] vettore;
//		vettore = leggiVettore();
		
		int[] vettore = new int[10];
		riempiVettoreRandom(vettore, 1000);
		
		stampaVettore(vettore);
		sort(vettore);
		System.out.println();
		stampaVettore(vettore);
		System.exit(0);
	}
}