Mergesort Sortieralgorithmus

In diesem Video präsentiert Prof. Dr. Oliver Lazar den Sortieralgorithmus MergeSort. Neben einer kleinen Demonstration des Ablaufs mit Hilfe eines Kartenspiels wird auch das Laufzeitverhalten erläutert.
Quellcode: www.nerdwest.de

[@TheStewie96]

Vielen Dank für Ihre tolle Erklärung!!!

[@martinsgaming-kanal7727]

Es gibt von Mergesort aber noch eine andere Variante, die auch einfacher zu programmieren ist: Die Anzahl der Listen ist dabei gleich zu Beginn identisch mit der Anzahl der zu sortierenden Elemente. In jedem Durchlauf werden dann immer zwei benachbarte Listen zu einer neuen zusammengerechnet. Bei einer ungeraden Anzahl, bleibt die letzte Liste unbearbeitet. Die Sortierung ist dann beendet, wenn es nur noch eine Liste gibt. Die Anzahl der Vergleiche und Vertauschungen / Kopien, ist in beiden Fällen aber identisch. Die hier von mir beschriebene Variante, ist aber vom Grundsatz her immer ganz minimal schneller und sie basiert auch nicht auf dem Prinzip von "teile-und-herrsche".