Мерг сорт

 #include <stdio.h>

// Функция слияния, которая использует уже готовый внешний буфер temp

void merge(int arr[], int temp[], int left, int mid, int right) {

    int i = left;     // Индекс для левой половины

    int j = mid + 1;  // Индекс для правой половины

    int k = left;     // Индекс для записи в буфер

    // Сравниваем элементы из двух половин и копируем меньший в temp

    while (i <= mid && j <= right) {

        if (arr[i] <= arr[j]) {

            temp[k++] = arr[i++];

        } else {

            temp[k++] = arr[j++];

        }

    }

    // Копируем оставшиеся элементы из левой половины (если есть)

    while (i <= mid) {

        temp[k++] = arr[i++];

    }

    // Копируем оставшиеся элементы из правой половины (если есть)

    while (j <= right) {

        temp[k++] = arr[j++];

    }

    // Переносим упорядоченные элементы обратно в исходный массив

    for (i = left; i <= right; i++) {

        arr[i] = temp[i];

    }

}

// Рекурсивная функция сортировки с передачей буфера temp

void mergeSort(int arr[], int temp[], int left, int right) {

    if (left < right) {

        int mid = left + (right - left) / 2;

        // Рекурсивно делим массив пополам

        mergeSort(arr, temp, left, mid);

        mergeSort(arr, temp, mid + 1, right);

        // Сливаем части, используя выделенный temp

        merge(arr, temp, left, mid, right);

    }

}

int main() {

    int arr[] = {38, 27, 43, 3, 9, 82, 10};

    int size = sizeof(arr) / sizeof(arr[0]);

    // Создаем один временный массив на стеке нужного размера

    // Для 40-100 элементов это абсолютно безопасно и быстро

    int temp[100]; 

    printf("Исходный массив: ");

    for (int i = 0; i < size; i++) printf("%d ", arr[i]);

    printf("\n");

    // Запускаем сортировку, передавая буфер temp

    mergeSort(arr, temp, 0, size - 1);

    printf("Отсортированный массив: ");

    for (int i = 0; i < size; i++) printf("%d ", arr[i]);

    printf("\n");

    return 0;

}