Witam!
Ostatnio przypominam sobie algorytmy i mamy sobie takie sortowanie przez scalanie. Napisałem kod w C++ ale w żaden sposób nie mogę dopatrzeć się błędu. Sortowanie oczywiście nie działa - dostaję nieuporządkowany ciąg albo pojawiają się powielone wartości.
void merge(int a[], int f, int q, int b){
int lsize = q - f + 1;
int rsize = b - q;
int * l = new int[lsize];
int * r = new int[rsize];
for(int i = 0; i < lsize; ++i)
l[i] = a[f + i];
for(int i = 0; i < rsize; ++i)
r[i] = a[q + i];
int i, j;
i = j = 0;
for(int k = f; k < b; ++k){
if(l[i] <= r[j])
a[k] = l[i++];
else
a[k] = r[j++];
}
delete [] l;
delete [] r;
}
void merge_sort(int a[], int f, int b){
if(f < b){
int q = (f + b) / 2;
merge_sort(a, f, q);
merge_sort(a, q + 1, b);
merge(a, f, q, b);
}
}
Naprawdę nie widzę co tu jest nie tak, a leciałem debuggerem nie raz i dalej nie wiem. Dajcie jakąś wskazówkę, bo chyba już ślepy jestem ;)
pozdrawiam.