Учебная версия на русском. Код и его вывод сохранены в исходном виде.

Сортировка слиянием на C

Разделяйте, сортируйте и объединяйте массивы за O(N log N).

Merge sort делит диапазон пополам до частей из одного элемента. При возврате из рекурсии две упорядоченные части сливаются: каждый раз выбирается меньший из первых ещё не обработанных элементов.

После основного цикла скопируйте оставшиеся элементы любой половины. Если при равенстве первым выбирать элемент левой половины, сортировка может быть стабильной. Обычная реализация требует O(N) дополнительной памяти и стека рекурсии.

Проверьте нечётные размеры, одинаковые значения и границы временного буфера. Без дополнительных оптимизаций время остаётся O(N log N), даже если вход уже упорядочен.

Код C

#include <stdio.h>
#include <stdlib.h>

int merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

    if (L == NULL || R == NULL) {
        free(L);
        free(R);
        return 0;
    }

    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];

    free(L);
    free(R);
    return 1;
}

int mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        if (!mergeSort(arr, l, m) || !mergeSort(arr, m + 1, r)) return 0;
        return merge(arr, l, m, r);
    }
    return 1;
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    if (!mergeSort(arr, 0, n - 1)) {
        fputs("Memory allocation failed.\n", stderr);
        return EXIT_FAILURE;
    }
    printf("MergeSorted Array:\n");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Открыть в компиляторе

Ожидаемый вывод

MergeSorted Array:
3 9 10 27 38 43 82

Частые вопросы

Почему код и вывод остаются на английском?

Ключевые слова, идентификаторы и строки, проверяемые тестами, сохранены, чтобы не менять программу. Объяснения и элементы управления переведены.