Mergesort (zyklische Liste)

[pauser]

Hi!
Ich muss eine (zyklische)DoppeltVerketteListe mit MergeSort sortieren !
Das ist mein Kod bisher:

public class Sorter {
    public DoublyLinkedList mergesort(DoublyLinkedList in, int numOfElements) {
        in.first = split(in.first, 1,numOfElements);
        return in;
    }
    
    private ListElement split(ListElement first, int l, int r){
        if(l<r){ 
            int m = (l+r)/2;
            ListElement left = first;
            ListElement right = first;
            for(int i=1;i<=m;i++){
            right = right.next;
            }
            ListElement r_left = split(left,l,m);
            ListElement r_right = split(right,m+1,r);
            return merge(r_left,r_right);
        }
        return first;
    }

    private ListElement merge(ListElement left, ListElement right){
        System.out.println("left="+left+" right="+right);
        return right;
    }

}

Input:

1
2
3
4
5
6

output:

left=1 right=2
left=2 right=3
left=4 right=2
left=2 right=3
left=3 right=3

Die Idee von split-methode geht theoretisch glaube ich aber wenn ich das programm probiere dann bekomme ich mehr output als ich erwarte.
Meine Fragen sind :
Ist die Funktion split richtig , und nach jedem rekursiven aufruf von split(), wird marge() aufgerufen, also ich kann momentan nur nach jedem aufruf 2 elemente zusammenbringen.
Wie tue ich dass ich alle elemente wieder zusammen mache ?


Information:
Die Klasse ListElement hat einen pointer ListElement next und einen pointer ListElement prev.
Die Klasse DoublyLinkedList ist nur der Kopf der Liste, drinne hat sie einen ListElement first.

Hifft mir bitte, ich brauche es nubedingt !

 

[pauser]

Hat jemand eine Antwort ?!

 

[SlaterB]

hättest du nicht bereits nach 2 Stunden etwas gepostet, dann wäre dein Thema in der Liste der Unbeantworteten Themen prominent besetzt,
so bin ich nur per Zufall beim normalen Durchlauf aller Themen drauf gestoßen..

> bekomme ich mehr output als ich erwarte.
was erwartest du denn? wieso verschweigst du diese Information?
andere können das sicher im Kopf nachrechnen (nicht im Programm, du sparst dir die Main-Methode, die Listen-Klasse usw.), aber das ist eine Aufgabe für dich

> left=4 right=2
sieht sicherlich nicht gut aus

>for(int i=1;i<=m;i++){
> right = right.next;
ok, doch noch was gesehen, hier musst du wohl von i=l (ellll für links) starten, nicht von i=1 (eins für Anfang der Liste)

----

merge() hast du noch gar nicht, das wird dir hier aber niemand programmieren,
schau dir Mergesort im Internet an