Iteratives Mergesort

[RTC]

Hi Leute.

Ich hatte versucht aus dem rekursiven Mergesort ein iteratives zu machen, aber irgendwie funktioniert folgendes Programm nur bedingt:

#include <stdio.h>

int *b;

void mergesort_it(int a[], int n){              //n=Elementezahl
    int step, i, j, k, m, l, r;
    n--;                                        //erfordert weniger Arbeit
    for(step=1; step<n*2; step*=2){             //verdopple sequentiell die Dateilänge
        r=0;                                    //Anfangswert für rechte Grenze
        while(r<n){                             //solange Folge nicht komplett betrachet
            l=(!r)?0:(r+1);                     //linken Rand auf bisher rechte Grenze+1
            r+=step;                            //rechten Rand um step erhöhen
            m=(l+r)/2;                          //Mitte finden
            if(r>n)                             //wenn über das Ziel hinaus geschossen
                r=n;                            //dann auf letztes Element setzen
            for(i=m+1; i>l; i--) b[i-1]=a[i-1]; //linke  Teildatei in Hilfsarray
            for(j=m; j<r; j++) b[r+m-j]=a[j+1]; //rechte Teildatei umgedreht in Hilfsarray
            for(k=l; k<=r; k++)
            a[k]=(b[i]<b[j])?b[i++]:b[j--];     //füge sortiert in a ein
        }
    }
}

int main(void){
	int i, n=20;
	b=(int*)malloc(n*sizeof(int));
	int a[]={3, 42, 22, 49, 26, 13, 23, 10, 46, 21, 14, 1, 36, 27, 36, 25, 28, 8, 10, 15};
	srand(time(0));

	printf("Ausgangsfolge:\n");
	for(i=0; i<n; i++)
		printf("%d, ",a[i]);

	mergesort_it(a,n);
	printf("\b\b  \n\nSortierte Folge:\n");
	for(i=0; i<n; i++)
		printf("%d, ",a[i]);
	printf("\b\b  \n\n");

	free(b);
	return 0;
}

Wenn in a mehr als 17 Elemente sind, dann ist die erste zurück gelieferte Zahl undefiniert. Ich kann mir aber leider nicht vorstellen warum?!

Wäre schön, wenn mal einer von euch weiter wissen würde - auch im Internet gibt es zum iterativen Mergesort kaum brauchbaren Code...

[RTC]

Ok, folgende Version der Funktion funktioniert schon besser, bringt aber immernoch nicht exakt die richtigen Ergebnisse. Ich denke, es hängt damit zusammen, dass das Zusammenfügen zweier Dateien im letzten Teil der Folge nicht mehr "step" entspricht, also keine exakte Länge von 2,4,8,16... mehr hat. Mal schauen, ob ich noch zu einem richtigen Ergebnis komme, aber hat vielleicht jemand von euch schonmal eine funktionierende Variante?

void mergesort_it(int a[], int n){              //n=Elementezahl
    int step, i, j, k, m, l, r;
    n--;                                        //erfordert weniger Arbeit
    for(step=1; step<n*2; step*=2){             //verdopple sequentiell die Dateilänge
        r=-1;                                   //Anfangswert für rechte Grenze
        while(r<n){                             //solange Folge nicht komplett betrachet
            l=r+1;                              //linken Rand auf bisher rechte Grenze+1
            r+=step;                            //rechten Rand um step erhöhen
            m=(l+r)/2;                          //Mitte finden
            if(r>n)                             //wenn über das Ziel hinaus geschossen
                r=n;                            //dann auf letztes Element setzen
            for(i=m+1; i>l; i--) b[i-1]=a[i-1]; //linke  Teildatei in Hilfsarray
            for(j=m; j<r; j++) b[r+m-j]=a[j+1]; //rechte Teildatei umgedreht in Hilfsarray
            for(k=l; k<=r; k++)
                a[k]=(b[i]<b[j])?b[i++]:b[j--]; //füge sortiert in a ein
        }
    }
}

[RTC]

Alles klar, habe mal ne Nacht drüber geschlafen. Hatte nur einen Fakt übersehen, der das Berechnen der Mitte m betraf.
Jetzt geht es...

void mergesort_it(int a[], int n){              //n=Elementezahl
    int step, i, j, k, m, l, r;
    for(step=2; step<n*2; step*=2){             //verdopple sequentiell die Dateilänge
        r=-1;                                   //Anfangswert für rechte Grenze
        while(r<n){                             //solange Folge nicht komplett betrachet
            l=r+1;                              //linken Rand auf bisher rechte Grenze+1
            r+=step;                            //rechten Rand um step erhöhen
            m=(l+r)/2;                          //Mitte finden
            if(r>n){                            //wenn über das Ziel hinaus geschossen
                r=n;                            //dann auf letztes Element setzen
                if(m>r) m=(l+r)/2;              //wenn Mitte hinter r liegt, neu berechnen
            }
            for(i=m+1; i>l; i--) b[i-1]=a[i-1]; //linke  Teildatei in Hilfsarray
            for(j=m; j<r; j++) b[r+m-j]=a[j+1]; //rechte Teildatei umgedreht in Hilfsarray
            for(k=l; k<=r; k++)
                a[k]=(b[i]<b[j])?b[i++]:b[j--]; //füge sortiert in a ein
        }
    }
}