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

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

В общем пытался сам написать сортировку слиянием, в результате потерял литр крови из глаз. Моя программа вышла чересчур большой и неадекватной. Хотел поискать решения в интернете и нашел их великое множество, но все они на с++, а работающую программу на чистом си не встретил. Из-за плохого знания с++, не смог перевести на си. Пожалуйста, если знаете, где есть работающая версия, скиньте ссылку или код. Вот хороший сайт, но там решение на си++, времени разбираться с классами нет, помогите, будьте добры.

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

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

#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;
}

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

Этот код реализует сортировку массива целых чисел слиянием. Он использует многопоточность для ускорения процесса сортировки.

В функции mergesort происходит сортировка массива a с помощью алгоритма сортировки слиянием. Эта функция принимает аргумент arg, который является структурой str_k, содержащей два индекса, ограничивающие подмассив, который нужно отсортировать.
В функции mergesort_1 происходит сортировка массива a с помощью алгоритма сортировки слиянием. Эта функция принимает аргумент step, который определяет размер подмассива, который нужно отсортировать на каждом шаге.
В функции main происходит чтение чисел из файла в массив a. Затем определяется количество потоков, которые будут использоваться для сортировки. Создаются потоки и запускается сортировка слиянием в каждом потоке. Затем происходит объединение массива a из всех потоков. Результат сортировки записывается в файл answer.txt.
Значения переменных:
- MAXLEN - максимально возможный размер массива a.
- NANO - используется для точного вычисления времени работы программы.
- len - количество элементов в массиве a.
- for_8Cores - временный массив, используемый для сортировки.
- cer - размер подмассива, который сортируется в каждом потоке.
- k - структура, используемая для передачи границ подмассивов в функцию сортировки.
- thread - массив потоков.
- tp - структура, используемая для измерения времени работы программы.
- start - время начала выполнения программы.
- Nstart - время начала выполнения программы в наносекундах.
- f - файл, используемый для чтения чисел и записи результата сортировки.
- i - счетчик, используемый для итерации по массиву a и файлу f.
- cores - количество потоков, которые будут использоваться для сортировки.