Doppelt verkettete Liste sortieren

[Sidorion]

Bau Dir einen sortierten Binärbaum auf. Jetzt kannst Du Deine Elemente der doppelten Liste eins nach dem anderen in den Baum stecken und aus diesem Baum dann wieder eine doppelte Liste zusammenstellen.
Das geht so: das erste Element der Liste wird die Wurzel. das zweite wird verglichen und wenns kleiner ist, wird es das linke Kind, ansonsten das Rechte. Ist das jeweilige Kind schon besetzt, dann wird mit diesem wieder verglichen usw.
Wenn der Baum fertig ist, fängst Du gaaaanz links an. Dies ist das kleinste Element und kommt als erstes in die neue Liste. Danach sein Elternknoten. Hat dieser ein rechtes Kind, gehst Du in diesem rechten Teilbaum gaaaanz nach links usw.

Damit die Einfügesuche beschleunigt wird, kannst Du die Tiefe des Baumes reduzieren, indem Du nach jedem Einfügen den Baum austarierst. Dazu solltest Du aber mal nach nem Tut über Binärbäume suchen, das würde hier zu weit führen.

Dieses Verfahren hätte wenigstens nur O=n*lb(n), im Gegensatz zu bubbleSort (n^2). Der ist der einzige, der mir gerade einfällt, der auch ohne Indexierung auskommt.

Ach ja: und sorge dafür dass die Anzahl der Elemente jedes Elements nur einmal berechnet wird, das spart auch ganz schön Zeit.