/* ordinamento per fusione
 * versione semplificata che usa due array di appoggio
 */
 
public class MergeSortSemplice
{
	public static void fusione(double[] a, double[] b, double[] ris)
	{
		
		int i=0, j=0, k=0;
		
		while(i<a.length && j<b.length)
		{
			if(a[i]<b[j])
			{
				ris[k]=a[i];
				k++;
				i++;
			}
			else
			{
				ris[k]=b[j];
				k++;
				j++;
			}
		}
		
		if(i==a.length)
			while(j<b.length)
			{
				ris[k]=b[j];
				k++;
				j++;
			}
		else
			while(i<a.length)
			{
				ris[k]=a[i];
				k++;
				i++;
			}

	}
	
	
	public static void stampaArrayInRiga(double[] v)
	{
		for(int i=0; i<v.length; i++)
			System.out.print("\t" + v[i]);
		System.out.println();
	}


	public static void ordina(double[] v)
	{
		
	// passo base della ricorsione: array di lunghezza al piu' 1
		if(v.length<=1)
			return;
		else
		{
			double[] v1 = new double[v.length/2];
			double[] v2 = new double[v.length - v1.length];
			
	// copia prima meta' in v1
			for(int i=0; i< v1.length; i++)
				v1[i] = v[i];
	// copia parte rimanente  in v2
			for(int i=0; i< v2.length; i++)
				v2[i] = v[i + v1.length];
			
	// chiamate ricorsive per ordinare le due meta'	
			ordina(v1);
			ordina(v2);
			
	// ricombinazione dei due array ordinati
			fusione(v1, v2, v);
			
			return;
		}
	}

	public static void main(String[] args)
	{
		double[] x={ 13, 5.6, 1.3, 4.5, 12, 15.6, 5.9};
		
		stampaArrayInRiga(x);

		ordina(x);

		stampaArrayInRiga(x);
		
		System.exit(0);
	}
}