Sortierverfahren

Natural Mergesort

Natural Mergesort ist eine Variante des iterativen Mergesort-Verfahrens. Der Grundgedanke besteht darin, in der zu sortierenden Folge "natürlich" vorkommende, bereits sortierte Teilstücke auszunutzen.

Beispiel: In der Zahlenfolge

6 8 2 4 1 3 5 7

sind folgende bereits sortierte Teilstücke enthalten:

6 8, 2 4 und 1 3 5 7.

Mergesort dagegen nimmt keine Rücksicht auf bestehende Vorsortierungen, sondern durchläuft stets alle log(n) Iterationsebenen. In dem Beispiel etwa würden auf der ersten Ebene die 6 und die 8 zu dem sortierten Teilstück 6 8 verschmolzen, obwohl dieses Teilstück auch vorher schon sortiert war.

Durch das Ausnutzen bestehender Vorsortierungen lassen sich bei Natural Mergesort gegebenenfalls Merge-Schritte einsparen. Im besten Fall, wenn die Folge nur aus konstant vielen sortierten Teilstücken besteht, sind nur konstant viele Merge-Schritte erforderlich, sodass sich eine Zeitkomplexität von Θ(n) ergibt. Im schlechtesten Fall hat Natural Mergesort allerdings dieselbe Zeitkomplexität wie Mergesort, nämlich Θ(n log(n)).

Um die Implementierung zu vereinfachen, werden ähnlich wie bei der Variante c von Mergesort jeweils gegenläufig sortierte Teilstücke verschmolzen. Dies hat zusätzlich den Vorteil, dass auch absteigend vorsortierte Teilstücke ausgenutzt werden können.

Definition: Sei a = a₀, ..., a_n-1 eine Folge. Ein Teilstück a_i, ..., a_i+k, k ∈ ℕ₀ heißt bitonischer Lauf, wenn es ein m ∈ ℕ₀, m≤k gibt, sodass gilt

a_i ≤ a_i+1 ≤ ... ≤ a_i+m ≥ a_i+m+1 ≥ ... ≥ a_i+k.

Ein bitonischer Lauf ist also ein Teilstück, das zuerst monoton steigt und dann monoton fällt (daher bitonisch). Aber auch ein rein monoton steigendes Teilstück ist ein bitonischer Lauf (bei dem m = k ist), ebenso ein rein monoton fallendes Teilstück (m = 0).

Beispiel: Die Zahlenfolge

6 8 2 4 1 3 5 7

hat die bitonischen Läufe

6 8 2, 4 1 und 3 5 7.

In der folgenden Implementation von Natural Mergesort werden im ersten Schritt die vorhandenen bitonischen Läufe ausfindig gemacht. In den weiteren Iterationsschritten werden diese abwechselnd zu aufsteigend bzw. absteigend sortierten Teilstücken verschmolzen, sodass hierdurch wiederum, nunmehr längere, bitonische Läufe zustande kommen. Am Ende ist die gesamte Folge sortiert.

Genau wie Mergesort benötigt auch Natural Mergesort ein zusätzliches Array b. Die Funktion mergeruns sucht bitonische Läufe im Array a und verschmilzt sie zu sortierten Teilstücken. Diese Teilstücke werden abwechselnd aufsteigend und absteigend sortiert in das Array b geschrieben, sodass dort neue bitonische Läufe entstehen. Die Funktion gibt true zurück, wenn das ganze Array b aufsteigend sortiert ist.

Die Prozedur merge verschmilzt einen bitonischen Lauf zu einem sortierten Teilstück. Der Parameter asc bestimmt die Sortierrichtung.

Die Prozedur naturalmergesort ruft solange mergeruns auf, bis die Folge sortiert ist. Hierbei wechseln die Rollen des ursprünglichen Arrays a und des Hilfsarrays b sich ab.

Die folgende Klasse NaturalMergeSorter kapselt die genannten Funktionen. Die Methode sort übergibt das zu sortierende Array an das Array a und ruft naturalmergesort auf.

Mit der Anweisung

NaturalMergeSorter s=new NaturalMergeSorter();

wird ein Objekt vom Typ NaturalMergeSorter angelegt. Mit

s.sort(c);

kann anschließend ein Array c sortiert werden.

Es folgt das Programm. In Java bedeutet die bedingte Zuweisung c=asc? 1: -1; dasselbe wie if (asc) c=1; else c=-1;. Die Anweisung x=a[i++]; ist äquivalent zu der Anweisungsfolge x=a[i]; i=i+1;. Die Kurzschreibweise k+=c; bedeutet k=k+c;.

public class NaturalMergeSorter
{
    private int[] a;
    private int[] b;    // Hilfsarray
    private int n;

    public void sort(int[] a)
    {
        this.a=a;
        n=a.length;
        b=new int[n];
        naturalmergesort();
    }

    private boolean mergeruns(int[] a, int[] b)
    {
        int i=0, k=0, x;
        boolean asc=true;

        while (i<n)
        {
            k=i;
            do x=a[i++]; while (i<n && x<=a[i]);  // aufsteigender Teil
            while (i<n && x>=a[i]) x=a[i++];      // absteigender Teil
            merge (a, b, k, i-1, asc);
            asc=!asc;
        }
        return k==0;
    }

    private void merge(int[] a, int[] b, int lo, int hi, boolean asc)
    {
        int k=asc? lo: hi;
        int c=asc? 1: -1;
        int i=lo, j=hi;

        // jeweils das nächstgrößte Element zurückkopieren,
        // bis i und j sich überkreuzen
        while (i<=j)
        {
            if (a[i]<=a[j])
                b[k]=a[i++];
            else
                b[k]=a[j--];
            k+=c;
        }
    }

    private void naturalmergesort()
    {
        // abwechselnd von a nach b und von b nach a verschmelzen
        while (!mergeruns(a, b) & !mergeruns(b, a));
    }

}    // end class NaturalMergeSorter

In dieser Implementierung werden die bitonischen Läufe durch mergeruns jedes Mal neu gesucht. Dies ist eigentlich nur beim ersten Mal notwendig, danach sind die jeweils neu gebildeten bitonischen Läufe ja bekannt. Man könnte ihre Anfangs-Indexpositionen in einer Warteschlange (Queue) für den nächsten Durchlauf von mergeruns speichern. Die asymptotische Zeitkomplexität ändert sich allerdings hierdurch nicht.

Die Funktion mergeruns halbiert bei jedem Durchlauf die Anzahl der bitonischen Läufe. Sind zu Anfang r natürliche Läufe vorhanden, so sind damit Θ(log r) Aufrufe erforderlich, bis nur noch ein Lauf übrig ist. Da mergeruns in Zeit Θ(n) läuft, hat Natural Mergesort eine Zeitkomplexität von Θ(n log r).

Der schlechteste Fall tritt ein, wenn alle natürlich vorkommenden bitonischen Läufe die Länge 2 haben, z.B. wie in der Folge 1 0 1 0 1 0 1 0. Dann sind r = n/2 Läufe vorhanden, und Natural Mergesort benötigt genauso viel Zeit wie Mergesort, nämlich Θ(n log(n)).

Der günstigste Fall tritt ein, wenn die Folge nur aus konstant vielen bitonischen Läufen besteht. Dann ist nur Θ(n) Zeit erforderlich. Insbesondere ist dies der Fall, wenn die Folge bereits aufsteigend sortiert ist, wenn sie absteigend sortiert ist, wenn sie aus zwei sortierten Teilstücken besteht, oder wenn konstant viele Elemente in eine sortierte Folge einsortiert werden sollen.

Nachteilig ist, dass Natural Mergesort ebenso wie Mergesort einen zusätzlichen Speicherplatzbedarf von Θ(n) für das temporäre Array b hat.

[Knu 73] D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)

[Lan 12] H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Natural Mergesort und andere Sortierverfahren, so etwa Quicksort, Heapsort und Shellsort, finden Sie auch in meinem Buch über Algorithmen.
Weitere (vertikaler Abstand) Themen des Buches: Textsuche, Graphenalgorithmen, Arithmetik, algorithmische Geometrie, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Weiter mit: [Shellsort] oder [up]

H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 11.03.2001 Updated: 05.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden

Sortierverfahren

Natural Mergesort

Idee

Implementierung

Programm

Analyse

Literatur