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.
Dani H.
At Least I Can Say I Tried