Hallo,
ich versuche gerade mergesort zu implementieren. Das ist mein Versuch:
Eingabe:
[4, 2, 2, 8]
Ausgabe:
[2, 2, 2, 8]
Sieht vllt jmd das Problem. Ich würde mich sehr freuen
ich versuche gerade mergesort zu implementieren. Das ist mein Versuch:
Java:
public static <T extends Comparable<? super T>> void sort( List<T> list) {
mergesort(list,0, list.size()-1);
}
private static <T extends Comparable<? super T>> void mergesort (List<T> list, int p, int q) {
if(q-p<1) return;
int middle= (q+p)/2;
mergesort(list,p,middle);
mergesort(list, middle+1,q);
merge(list, p,middle,q);
}
private static <T extends Comparable<? super T>> void merge (List<T> list, int p, int middle, int r) {
List<T> left=new ArrayList<T>();
List<T> right=new ArrayList<T>();
for(int i=0; i<middle-p+1;i++) left.add(i, list.get(p+i));
for(int i=0; i<r-middle;i++) right.add(i, list.get(middle+i+1));
int leftindex=0;
int rightindex=0;
for(int i=p; i<r;i++) {
if(left.get(leftindex).compareTo(right.get(rightindex))<0)
list.set(i, left.get(leftindex++));
else list.set(i, right.get(rightindex++));
}
}
Eingabe:
[4, 2, 2, 8]
Ausgabe:
[2, 2, 2, 8]
Sieht vllt jmd das Problem. Ich würde mich sehr freuen