AuK/Teile und Herrsche 1 SS10/JavaMerge

Wiki-Quelltext dieser Seite.

<language>Java</language>
== Javabeispiel für Mergesort ==

<code id="4bbdfcc36a146">
    private int[] a;
    private int[] b;    // Hilfsarray
    private int n;

    public void sort(int[] a)
    {
        this.a=a;
        n=a.length;
        // je nach Variante entweder/oder:
        b=new int[(n+1)/2];    b=new int[n];
        mergesort(0, n-1);
    }

    private void mergesort(int lo, int hi)
    {
        if (lo<hi)
        {
            int m=(lo+hi)/2;
            mergesort(lo, m);
            mergesort(m+1, hi);
            merge(lo, m, hi);
        }
    }

    
public void merge(int lo, int m, int hi)
{
    int i, j, k;

    i=0; j=lo;
    // vordere Hälfte von a in Hilfsarray b kopieren
    while (j<=m)
        b[i++]=a[j++];

    i=0; k=lo;
    // jeweils das nächstgrößte Element zurückkopieren
    while (k<j && j<=hi)
        if (b[i]<=a[j])
            a[k++]=b[i++];
        else
            a[k++]=a[j++];

    // Rest von b falls vorhanden zurückkopieren
    while (k<j)
        a[k++]=b[i++];
}

</code>
<run id="4bc05e7d08c43">
int[] a = new int[]{5,4,8,2,1,6,2,12,34};
sort(a);
for(int i = 0 ; i < a.length ; i++){
System.out.print(a[i] + " ");
}
</run>

#Quelle: [http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/merge/merge.htm FH-Flensburg]