MergeSort rekursiv

[mlauX]

Hallo,

ich stehe grade irgendwie aufm Schlauch. Ich soll einen MergeSort implementieren, der Konstruktor füllt ein Array der Länge n mit Zufallszahlen von 0 bis 100. Funktioniert auch.

Nur irgendwie verstehe ich nicht, wie ich mit der Methode

void mergeSort(int lower, int upper)

arbeiten soll. Das Ganze soll halt rekursiv realisiert werden.

Wie der Algor. i.A. aussehen muss verstehe ich, aber wie die Rekursion genau ablaufen soll eben nicht.

Hier mal das, was ich schon gemacht habe.

public class MergeSort {
	int[] array;
	int[] left;
	int[] right;
	int[] newList;
	public MergeSort(int n) {
		array = new int[n];
		for(int i=0;i<array.length;i++) {
			double random = (Math.random()*101);
			int cast = Math.round((int)random);
			array[i] = cast;
			System.out.println("Array["+i+"]: "+array[i]);
		}
		
	}
	
	void mergeSort(int lower, int upper) {
		if(array.length == 1) {
			System.out.println("Fertig! "+array[0]);
		}else{
			left = new int[array.length/2];
			for(int j=0;j<array.length/2;j++) {
				left[j] = array[j];
				System.out.print(left[j]+", ");
			}
			System.out.println(" ");
			right = new int[array.length-left.length];
			for(int k=0;k<array.length-left.length;k++) {
				right[k] = array[(array.length/2)+k];
				System.out.print(right[k]+", ");
				//mergeSort(left.length,right.length);
			}
			System.out.println(" ");
			
		}
		for(int l=0;l<left.length;l++) {
			//da Eingabe immer gerade
			newList = new int[left.length*2];
			if(left[l] <= right[l]) {
				newList[l] = left[l];
				System.out.println(left[l] +"<="+ right[l]+": "+ +newList[l]);
			}else{
				newList[l] = right[l];
				System.out.println(right[l] +"<="+ left[l]+": "+newList[l]);
			}
			
		}
	}
}

Irgendwas stimmt da nicht. Ich muss ja zuerst per Rekursivenaufruf die Liste bis auf jeweils 1 Elt. splitten.

 

[bERt0r]

Eine kleine Hilfe:

public static int[] mergeSort(int[] arr)
	{	
		if(arr.length>1)
		{
			int split=arr.length/2;
			int arr1[]=Arrays.copyOfRange(arr, 0, split);
			int arr2[]=Arrays.copyOfRange(arr, split, arr.length);
		
			arr1=mergeSort(arr1);
			arr2=mergeSort(arr2);
			
			return mergeArrays(arr1, arr2);	
		}
		else
		{
			return arr;
		}
	}

 

[mlauX]

Danke. Aber so wie ich es verstehe, darf ich nur die obigen 2 Methoden verwenden.

Die 2. soll halt für den rekursiven Aufruf sein.