Основной цикл быстрой сортировки

Объединить все пары отсортированных частей массива:

Для t от 0 до q/2

Объединить

a(2tp)..a(2tp+p-1) и

a(2tp+p)..a(2tp+2p-1)

Переписать объединенный массив на место.

Пример программы:

// Функция объединяет два массива отсортированных по убыванию в один массив

// a, b - объединяемые массивы, c - результат, n - количество элементов в массивах а и b

void concatmas(int *a, int*b, int*c, int n)

{

int i=0, j=0, k=0;

while(i<n && j<n)

if(a[i]>b[j])

c[k++]=a[i++];

else

c[k++]=b[j++];

while(i<n)

c[k++]=a[i++];

while(j<n)

c[k++]=b[j++];

}

void quicksort(int *a, int *b, int n)

/* Выполняет быструю сортировку (слиянием)

a - сортируемый массив, b – промежуточный */

{

int t, p=1, q=n;

while(p<n)

{

#ifdef debug

printf("\np=%i, q=%i\n", p, q);

for(t=0; t<n; t++) printf("%i ", a[t]);

printf("\n");

#endif

for(t=0; t<q/2; t++)

concatmas(&a[2*t*p], &a[2*t*p+p], &b[2*t*p], p);

for(t=0; t<n; t++) a[t]=b[t];

p*=2; q/=2;

}

}

main()

{

int n = 8, i, ntest=4, it, f;

int c[4][8] = { {1, 2, 4, 4, 5, 6, 7, 8},

{8, 7, 6, 5, 4, 3, 2, 1},

{1, 2, 8, 7, 3, 4, 6, 5},

{1, 8, 2, 7, 3, 6, 5, 4} };

int d[4][8] = { {8, 7, 6, 5, 4, 4, 2, 1},

{8, 7, 6, 5, 4, 3, 2, 1},

{8, 7, 6, 5, 4, 3, 2, 1},

{8, 7, 6, 5, 4, 3, 2, 1} };

int a[8];

for(it=0; it<ntest; it++)

{

printf("\n\tTest %i\n", it);

printf("\nc=\n");

for(i=0; i<n; i++) printf("%i ", c[it][i]);

quicksort(c[it], a, n);

printf("\nc=\n");

for(i=0; i<n; i++) printf("%i ", c[it][i]);

f=0;

for(i=0; i<n; i++) if(c[it][i]!=d[it][i]) f=1;

if(f==0) printf("\ntest passed\n");

else printf("\ntest failed!\n");

}

}