Mergesort
Algorithmus Mergesort (F)
Falls F leer oder einelementig -> Fertig.
Divide: Teile F in 2 möglichst gleichgroße Hälften F1, F2.
Conquer: Sortiere L1 und L2 mittels Mergesort.
Merge: Verschmelze die sortierten Teillisten zu sortierter Liste.
Verschmelzen kann durch 2 Zeiger erfolgen, die die sortierten Teillisten durchwandern:
Zeigen zunächst auf erstes Element, vergleichen Schlüssel, tragen kleineres item in konstruierte Liste ein und bewegen den Zeiger auf dieses Element um eine Position weiter.