Problema Merge-Sort

[Darèios89]

Ho provato ad implementare un Merge-Sort, solo che forse non ho ben capito come funziona e quindi ho sbagliato ad implementarlo....:

public class MergeSort
{
	public static void main(String [] args)
	{
		int []a={3,6,5,7,9,8,0,5};
		int [] S=new int[a.length];
		MSort(a,0,a.length-1);
		
	}
	
	
	public static void merge(int [] a,int []b, int []S, int k)
	{
		int i=0;
		int j=0;
		k=0;
		
		
		while(i<a.length && j<a.length)
		{
			if(a[i]<b[j])
			{
				S[k++]=a[i];
				i=i++;
			}
			else if(a[i]>b[j])
			{
				S[k++]=b[j];
				j=j++;
			}
		}
		
		while(i<a.length)
		{
			S[k++]=a[i];
			i=i++;
		}
		
		while(j<b.length)
		{
			S[k++]=b[j];
			j=j++;
		}
	}
	
	
	public static int MSort(int [] a,int i, int f)
	{
		if(i>=f)
		{
			int m=(i+f)/2;
			return MSort(a,i,m);
			return MSort(a,m+1,f);
			merge(a,b);
		}
	}
	
		
}

Giustamente mi dà errore nel metodo MSort perchè non trova la variabile b.
Però non ho capito a questo punto come implementarlo, cioè come faccio a passargli il sottoarray?

[Naruto 92]

dichiarati un vettore di nome b di interi come variabile d'istanza.

inoltre, nel tuo metodo Msort dovresti avere un solo return perchè, come penso saprai, il return costituisce la fine di un metodo in quanto le istruzioni dopo di esso non verranno mai eseguite.
poi, sempre nell'Msort, invochi il metodo merge con 2 parametri quando questo ne richiede 4.

[M@P]

Ti suggerisco di vederti questa pagina di Wikipedia, dove oltre a capire come funziona il Merge Sort, puoi anche vedere un esempio di pseudo-codice che non ti sarà difficile mutare in codice Java.

[Darèios89]

Si però...non ho ben capito come funzionano su Wikipedia left e rigth, dovrebbe tenere conto di quanti elementi ci sono nella parte sinistra dell'array e nella destra?
Come faccio a farlo capire al metodo passandoglielo come parametro?
L'ho cambiato così ma rimangono tanti problemi, come faccio a farlo funzionare se non conosco la dimensione ,a la metà su cui operare....

public class MergeSort
{
	public static void main(String [] args)
	{
		int []a={3,6,5,7,9,8,0,5};
		int [] S=new int[a.length];
		int []b;
		MSort(a,0,a.length-1);
		
	}
	
	
	public static void merge(int [] a,int [] b,int []S, int left,int center, int right)
	{
		int i= left;
		int j=center+1;
		int k=0;
		
		
		while(i<center && j<right)
		{
			if(a[i]<b[j])
			{
				S[k++]=a[i];
				i=i++;
			}
			else if(a[i]>b[j])
			{
				S[k++]=b[j];
				j=j++;
			}
		}
		
		while(i<a.length)
		{
			S[k++]=a[i];
			i=i++;
		}
		
		while(j<b.length)
		{
			S[k++]=b[j];
			j=j++;
		}
	}
	
	
	public static void MSort(int [] a,int left, int right)
	{
		if(left>=right)
		{
			
				int center=(left+right)/2;
			
				MSort(a,left,center);
				MSort(a,center+1,right);
				merge(a,b,S,left,center,right);
		}
	}
	
		
}

[Darèios89]

Ora di compilare compila, però non so se è corretto......come faccio a stampare l'array ordinato?

public class MergeSort
{
	
	public static void main(String [] args)
	{
		int [] a={3,6,5,7,9,8,0,5};
		MSort(a,0,a.length-1);
		for(int i=0; i<a.length; i++)
	}
	
	
	public static void merge(int [] a, int left,int center, int right)
	{
		int [] S=new int[a.length-1];
		int i= left;
		int j=center+1;
		int k=0;
		
		while(i<center && j<right)
		{
			if(a[i]<a[j])
			{
				S[k++]=a[i];
				i=i++;
			}
			else if(a[i]>a[j])
			{
				S[k++]=a[j];
				j=j++;
			}
		}
		
		while(i<center)
		{
			S[k++]=a[i];
			i=i++;
		}
		
		while(j<right)
		{
			S[k++]=a[j];
			j=j++;
		}
		a=S;
		
	}
	
	
	public static void MSort(int [] a,int left, int right)
	{
		if(left<right)
		{
			
			int center=(left+right)/2;
				MSort(a,left,center);
				MSort(a,center+1,right);
				merge(a,left,center,right);
			
		}
	
	}
}

[Darèios89]

Mi sapreste dare un suggerimento?

[Naruto 92]

la prima idea che mi viene in mente è quella di crearti un array momentaneo, contenente i valori in modo ordinato e poi stamparlo

[Darèios89]

Più esattamente dove lo inseriresti?
In quale metodo?

Sto provando ma...non riesco a metterlo e a farlo funzionare, perchè non lo trovano i metodi, ho le idee un pò confuse..

[Naruto 92]

nel metodo che vuoi che te li stampi in ordine