mergesort

#include <stdio.h>

void sort(int *arr, int start, int end) {
    if (start == end) return;

    int mid = (start + end) / 2;
    sort(arr, start, mid);
    sort(arr, mid + 1, end);

    int temp[end - start + 1];
    int i1 = start, i2 = mid + 1;
    int k = 0;

    while (i1 <= mid && i2 <= end) {
        if (arr[i1] < arr[i2]) {
            temp[k++] = arr[i1++];
        } else {
            temp[k++] = arr[i2++];
        }
    }

    while (i1 <= mid) {
        temp[k++] = arr[i1++];
    }

    while (i2 <= end) {
        temp[k++] = arr[i2++];
    }

    for (int i = 0; i < k; i++) {
        arr[i + start] = temp[i];
    }
}

int main() {
    int n;
    scanf("%d", &n);

    int a[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    sort(a, 0, n - 1);

    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }

    printf("\n");

    return 0;
}