zum Inhalt springen

Mergesort

Links:

http://de.wikipedia.org/wiki/Mergesort

 

C++ Quellcode

// **************************************
// mergesort
void merge(int* A, int l, int m, int r)
{
    int i=l, j=m+1, k=l;
    int T[r+1];                         // sort. Teilfolge > T

    while((i<=m)&&(j<=r))
    {
        if(A[i]<A[j])    { T[k]=A[i]; i++; }
        else               { T[k]=A[j]; j++; }
        k++;
    }

    while(i<=m)           { T[k]=A[i]; k++; i++; }
    while(j<=r)            { T[k]=A[j]; k++; j++; }
    for(i=l; i<=r; i++)      A[i]=T[i];            // ganze Folge tauschen
}

void mergesort(int* A, int l, int r)
{
    int m;
    if(l<r)
    {
        m=(l+r)/2;
        mergesort(A,l,m);
        mergesort(A,m+1,r);
        merge(A,l,m,r);
    }
}


// **************************************
//
int main()
{
    int A[]={8,5,6,3,4,2,1};
    int n=sizeof(A)/sizeof(int);
    mergesort(A,0,n-1);
}