Нужен пример сортировки слиянием - C (СИ) (76012)

Формулировка задачи:

Ребят напишите пожалуйста сортировку слиянием???

Решение задачи: «Нужен пример сортировки слиянием»

Листинг программы

#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <pthread.h>
#include <time.h>
#define MAXLEN 100000000
#define NANO 1000000000
 
 
struct timespec tp;
 
 
int a[MAXLEN], len;
int *for_8Cores; // like a buf
typedef struct {
    int a;
    int b;
} str_k;
 
void *mergesort (void *arg) {
    str_k kk = * (str_k *) arg;
    int step = 1;
    int k;
    int q;
    int i, j;
    while ((kk.b - kk.a) > step) {
        
        for (k = kk.a; k < kk.b; k = k + 2 * step) {
            i = k;
            j = k + step;
            q = k;
            while ((i < k + step) && (i < kk.b) && (j < k + 2 * step) && (j < kk.b)) {
                if (a[i] <= a[j]) {
                    for_8Cores[q] = a[i];
                    ++i;
                    ++q;
                }
                else {
                    for_8Cores[q] = a[j];
                    ++j;
                    ++q;
                }
            }
            while ((i < k + step) && (i < kk.b)) {
                for_8Cores[q] = a[i];
                ++q;
                ++i;
            }
            while ((j < k + 2 * step) && (j < kk.b)) {
                for_8Cores[q] = a[j];
                ++j;
                ++q;
            }
        }
        step *= 2;
                for (k = kk.a; k < kk.b; ++k)
                    a[k] = for_8Cores[k];
    }
}
 
void mergesort_1 (int step) {
    int k;
    int q;
    int i, j;
    int *buf;
    while (len > step) {            
        for (k = 0; k < len; k = k + 2 * step) {
            i = k;
            j = k + step;
            q = k;
            while ((i < k + step) && (i < len) && (j < k + 2 * step) && (j < len)) {
                if (a[i] <= a[j]) {
                    for_8Cores[q] = a[i];
                    ++i;
                    ++q;
                }
                else {
                    for_8Cores[q] = a[j];
                    ++j;
                    ++q;
                }
            }
            while ((i < k + step) && (i < len)) {
                for_8Cores[q] = a[i];
                ++q;
                ++i;
            }
            while ((j < k + 2 * step) && (j < len)) {
                for_8Cores[q] = a[j];
                ++j;
                ++q;
            }
        }
        for (k = 0; k < len; ++k)
            a[k] = for_8Cores[k];
        step *=2;
    }
}
 
int main (int argc, char **argv) {
    FILE *f;
    f = fopen (argv[1], "r");
    if (f == NULL) {
        printf ("There is no such file.\n");
        return 1;
    }
    int i;
    i = 0;
    while (fscanf (f, "%d", &a[i]) == 1) 
        ++i;
    len = i;
    fclose (f);
 
    int cores = atoi(argv[2]);
    if (cores < 1 || cores > 32) {
        printf ("Can't do this. It's immoral!\n");
        return 0;
    }
    printf ("working on %d thread(s)...\n", cores);
    for_8Cores = (int *) malloc (len * sizeof(int));
    pthread_t thread[16];
    int cer = 1;
    while (cer < len/cores) 
        cer *= 2;
    if ((len/cores - cer/2) <= (cer - len/cores))
        cer = cer/2;    
//  printf ("%d - cer\n", cer);
    str_k k[16];
    for (i = 0; i < cores - 1; ++i) {
        k[i].a = i * cer;
        k[i].b = (i + 1) * cer;
    }
    k[cores - 1].a = (cores - 1) * cer;
    k[cores - 1].b = len;
    clock_gettime (1, &tp);
    double start = tp.tv_sec;
    double Nstart = (double) tp.tv_nsec;
    for (i = 0; i < cores; ++i)
        pthread_create(&thread[i], NULL, mergesort, &k[i]);
    for (i = 0; i < cores; ++i)
        pthread_join(thread[i], NULL);
 
    mergesort_1 (cer);
    free (for_8Cores); //убрал за собой!
    f = fopen ("answer.txt", "w");
    for (i = 0; i < len; ++i)
        fprintf (f, "%d ", a[i]);
    fclose (f);
    clock_gettime (1, &tp);
    printf("Время работы = %lf\n", (double) (tp.tv_sec - start + ((double)tp.tv_nsec - Nstart) / NANO));
        
    return 0;
}

Объяснение кода листинга программы

Этот код реализует сортировку массива целых чисел слиянием. Вот список ключевых моментов:

В начале кода подключаются необходимые библиотеки: stdlib.h, fprintf, printf, malloc, pthread.h, time.h.
Затем определяются структуры и переменные, используемые в коде:
- struct timespec tp используется для измерения времени выполнения программы.
- int a[MAXLEN] - массив для сортировки.
- int *for_8Cores - буфер для временного хранения данных при сортировке во многопоточном режиме.
- typedef struct { int a; int b; } - структура str_k, используемая для передачи границ подмассивов на сортировку в многопоточном режиме.
- void *mergesort (void *arg) - функция сортировки слиянием, которая принимает аргумент типа void * и возвращает void *. Аргумент передается как структура str_k.
- void mergesort_1 (int step) - функция сортировки слиянием для одного потока, которая принимает шаг сортировки в качестве аргумента.
- int main (int argc, char **argv) - точка входа в программу. В этой функции происходит чтение массива из файла, установка количества потоков и запуск многопоточной сортировки.
Многопоточная сортировка реализована с использованием механизма потоков POSIX. Сначала создаются потоки, затем в каждом потоке вызывается функция mergesort, передавая ей границы подмассива для сортировки. После завершения всех потоков результаты объединяются в один массив.
Затем вызывается функция mergesort_1 для сортировки полученного массива с использованием заданного количества потоков.
Результат сортировки записывается в файл answer.txt.
В конце программы выводится время выполнения.