Für was out-of-place sortieren? InsertionSort is doch geradezu gemacht dafür Verkettete Listen zu sortieren... Warum? Verschieben is bei verketteten Listen O(1), bei arrays O(n)(naja nciht ganz, das wär jetzt worst-case. Im average-case isses etwas besser). Du kannst also annähernd linear sortieren! Jedenfalls in Bezug auch die Zuweisungen[1].
Alles was du dazu brauchst is ne Move-Prozedur/Methode. Die sieht ungefähr so aus:
Delphi-Quellcode:
// Pseudocode:
// Element entfernen:
VorherigesElement.Next := Element.Next;
// Element an der gegebenen Stelle einfügen:
Element.Next := ElementVorRichtigerPosition.Next;
ElementVorRichtigerPosition.Next := Element;
[1] Die Vergleiche sind da wider etwas schlechter, als bei den arrays, da der Zugriff aufwändiger ist. Da aber InsertionSort sowieso relativ wenige Vergleiche braucht, is InsertionSort in diesem Fall sehr gut geeignet...
mfg
Christian