Ok es tut sich doch noch ein Problem auf. Der Algo sortiert nicht richtig. Wo liegt denn der Fehler:
[CODE=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 i, int j) {
if (j-i < 1) return;
int mid = (i+j)/2;
mergesort(list, i, mid);
mergesort(list, mid+1, j);
merge(list, i, mid, j);
}
private static <T extends Comparable<? super T>> void merge(List<T> a, int p, int q, int r){
int half=q-p+1;
int otherhalf=r-q;
List<T> left=new ArrayList<T>();
List<T> right=new ArrayList<T>();
for(int i=0; i<half;i++) {
left.add(i,a.get(p+i));
}
for(int i=0; i<otherhalf;i++) {
right.add(i,a.get(q+i+1));
}
int leftindex,rightindex,resultindex;
leftindex=rightindex=resultindex=0;
// ein Array ist nichtleer
while(leftindex<left.size() || rightindex<right.size()) {
//beide Arrays haben Elemente
if(leftindex<left.size() && rightindex<right.size()) {
//beide Arrays enthalten Elemente
if(left.get(leftindex).compareTo(right.get(rightindex))<=0) {
a.set(resultindex,left.get(leftindex));
resultindex++;
leftindex++;
}
else {
a.set(resultindex,right.get(rightindex));
resultindex++;
rightindex++;
}
}
//linkes enthält Elemente
else if(leftindex< left.size()) {
a.set(resultindex,left.get(leftindex));
resultindex++;
leftindex++;
}
//rechtes enthält Elemente
else if(rightindex< right.size()) {
a.set(resultindex,right.get(rightindex));
resultindex++;
rightindex++;
}
}
}[/CODE]
