Mergesort

Mergesort: Variante f ohne explizites Auslagern

Bei der Standard­version des Sortier­verfahrens Mergesort wird in der Funktion merge die vordere Hälfte der Datenfolge in ein Hilfsarray ausgelagert. Anschließend werden die Daten­elemente der ausge­lagerten Hälfte und die der hinteren Hälfte ihrer Größe nach zurück­kopiert.

Es ist naheliegend, das Auslagern mit dem voraus­gehenden Rekursions­schritt zu kombinieren, indem das Hilfsarray zum Zielarray der Funktion merge gemacht wird.

Idee

Die folgende Implementation [Kloe 08] verwendet zwei Funktionen sortInPlace und sortInto.

In der Funktion sortInPlace wird zunächst die hintere Hälfte des Arrays a rekursiv mit sortInPlace an Ort und Stelle sortiert, unter Benutzung des Hilfsarrays b. Anschließend wird die vordere Hälfte mit sortInto ins Hilfsarray sortiert. Dies ist die Situation wie nach dem Auslagern der vorderen Hälfte in der Standard­version von Mergesort. Zum Schluss werden mit merge die Daten­elemente der ausge­lagerten Hälfte und die der hinteren Hälfte ihrer Größe nach ins Array a zurück­kopiert (Bild 1).

 

Bild 1: Funktion sortInPlace 

Bild 1: Funktion sortInPlace

 

In der Funktion sortInto wird die vordere Hälfte des Arrays a mit sortInPlace an Ort und Stelle sortiert, unter Benutzung des Hilfsarrays b. Dann wird rekursiv mit sortInto die hintere Hälfte ins Hilfsarray sortiert. Dies ist die Situation wie nach dem Auslagern der vorderen Hälfte in der Standard­version, jedoch mit vertauschten Rollen von Array a und Hilfsarray b. Zum Schluss werden mit merge die Daten­elemente ihrer Größe nach ins Hilfsarray b kopiert (Bild 2).

 

Bild 2: Funktion sortInto 

Bild 2: Funktion sortInto

 

Programm

Die folgende Implementierung in C++ wird erleichtert durch die C-typische Adressierung von Arrays wie z.B. im Aufruf sortInto(a+m, b+m, n-m).

 

void sort(int* a, int n)
{
    int m=(n+1)/2;
    int* b=new int[m];    // auxiliary array
    sortInPlace(a, b, n);
}

// sorts array a of length n in-place using array b as auxiliary array
void sortInPlace(int* a, int* b, int n)
{
    if (n<=1)
        return;

    int m=(n+1)/2;    // length of first half

    // sort second half of length n-m in-place using b as auxiliary array
    sortInPlace(a+m, b, n-m);

    // sort first half of length m, put result into b
    sortInto(a, b, m);

    merge(a, b, m, n);
}

// sorts array a of length n and puts the result into array b
void sortInto(int* a, int* b, int n)
{
    if (n<=0)
        return;

    int m=(n+1)/2;    // length of first half

    // sort first half of length m in-place using b as auxiliary array
    sortInPlace(a, b, m);

    // sort second half of length n-m, put result into second half of b
    sortInto(a+m, b+m, n-m);

    merge(b, a, m, n);
}

// merges array b and the second half of array a into array a 
void merge(int* a, int* b, int m, int n)
{
    int i, j, k;
    i=0; j=m; k=0;
    while (k<j && j<n)
        if (b[i]<=a[j])
            a[k++]=b[i++];
        else
            a[k++]=a[j++];

    while (k<j)
        a[k++]=b[i++];
}

Literatur

[Kloe 08]   T. Kloecker: (Persönliche Korrespondenz). Thomas Kloecker (2008)

 

 

Zurück zu Mergesort  oder   [up]

 

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