Doppelt verkettete Liste sortieren

[Noobinator]

Zitat von Dani:

Hallo, für verkettete Listen eignet sich Mergesort sehr gut. Laufzeit im worst case ist O(n*log(n)), also sehr nahe am theoretischen Minimum. Lineare Laufzeit, also O(n), wird schwer, da dein Wertebereich wahrscheinlich zu groß für Bucketsort ist.

Mergesort ist zwar ein rekursiver Algorithmus, allerdings garantiert er dir eine Rekursionstiefe von log(n). Wenn du also 1267650600228229401496703205376 Werte sortierst, hast du trotzdem nur eine Rekursionstiefe von ~100.

Ok danke dir erstmal =)
Werde ich mir mal zu Gemüte führen.

OT: endlich back @ Topic^^