Mergesort

Hinweise

  • Teilen Sie in der ersten Phase die Kartenstapel durch Klicks.
  • Führen Sie anschliessend jeweils die beiden zusammengehörenden Stapel zusammen.
  • Wählen Sie dabei die Kleinere der beiden zu Oberst auf dem Stapel liegenden Karten.
  • Mit dem Button x wird ein neues Kartenset bereitgestellt.
  • Mit - und + können kleinere oder grössere Kartensets bereitgestellt werden.

Zusatzinfos

Der Mergesort Algorithmus funktioniert nach dem "Teile und herrsche Prinzip". Dabei wird ein Problem solange in Teilprobleme zerlegt, bis diese einzeln gelöst - beherrscht - werden können. Durch die Lösung aller Teilprobleme, wird die Gesamtaufgabe gelöst.

Beim Mergesort kommt die Sortierung in der zweiten Phase zu Stande. Wird immer die kleinere Karte von den beiden Stapeln genommen, so ist zum Schluss der Gesamtstapel aufsteigend sortiert. Würde immer die grössere Karte genommen, so wäre der Stapel absteigend sortiert.

Dank des Teile und herrsche Prinzips ist der Mergesort Algorithmus sehr effizient und gehört zur Komplexitätsklasse "logarithmisch": O(log2(n)).