Sort-Merge-Algorithmus

Die Merge-Sortierung ist ein sort-Algorithmus  die darin besteht, zwei Listen zu einer zu verketten. Sein Prinzip basiert auf der Methode deviser pour régner. Der Vorteil von Sort-to-Merge ist, dass die beiden Listen gleichzeitig zusammengeführt werden, so dass wir eine Implementierung mit Threads durchführen können.

Der Algorithmus ist bekannt für seine Effizienz in Bezug auf Komplexität (Zeit und Speicher) und für das Sortieren von Listen:
  • Wir schneiden die Daten in zwei gleiche Teile.
  • Wir sortieren die Daten von jedem Teil (wir teilen jeden Teil auf, der Algorithmus wird rekursiv).
  • Wir führen die beiden Teile zusammen.
Wir tauschen das Startarray rekursiv in zwei Subarrays auf, bis das Array nur noch ein Element enthält. Sobald die Elemente unabhängig voneinander sortiert sind, wird ab diesem Zeitpunkt die Backtracking beginnt und wir werden die Untertabellen zusammenführen in eins, bis Sie das sortierte Startbrett erhalten. Die Zusammenführung besteht aus aufeinanderfolgenden Vergleichen.

Beispiel

Angenommen, wir möchten die folgende Tabelle sortieren: [ 38, 27 ,43, 3, 9, 82, 10]

Fusion in Java sortieren

Algorithm


TriFusion ALGORITHM (T, links, rechts);
    T: Wertetabelle;
    links, rechts: Ganzzahl;
    center: Ganzzahl;
NACH OBEN   
    IF (links < rechts) THEN
          ← Mitte (links + rechts) / 2;
          TriFusion (T, links, Mitte);
          TriFusion (T, Mitte + 1, rechts);
          MERGE(T, links, Mitte, rechts);
    FSI
FIN.