import javax.swing.JOptionPane;

/*
  Implementa l'ordinamento per fusione
*/		
public class MergeSortConMetodiEsterni
{

/*
	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 = Varie.leggiVettoreInt();
		
//		int[] vettore = new int[10];
//		Varie.riempiVettoreRandom(vettore, 1000);
		
		Varie.stampaVettore(vettore);
		sort(vettore);
		System.out.println();
		Varie.stampaVettore(vettore);
		System.exit(0);
	}
}