Sortierverfahren für Liste

[Gausi]

Insertionsort und Bubblesort lassen sich sehr einfach auf Listen implementieren. Hier werden immer nur benachbarte Elemente verglichen und vertauscht - kein Problem bei Listen.

Bei Quicksort laufen zwei "Zeiger" von vorne und hinten durch die Datenstruktur und vertauschen ggf. die Werte an den beiden Positionen - kein Problem mit Listen. Auch der rekursive Schritt ist mit Listen kein Problem.

Mergesort ist das einzige, wo man etwas mehr nachdenken könnte - hier kommt es auch auf die Variante an, die verwendet werden soll. Generell sollte aber der natürliche Mergesort (das ist die Variante, die Vorsortierungen berücksichtigt) aber auch mit Listen gehen - und da geht auch das mischen ohne zusätzlichen Speicher. (Man kann auch Arrays in Linearzeit auf konstantem Platz mischen, aber das ist nicht ganz trivial)

Wenn in der Liste noch ein Heapsort aufgeführt wäre, dann würde ich sagen: Der geht nicht (ohne weiteres) mit Listen. Wenn dann würde sich da ein Binärbaum anbieten.