请用C语言实现给定n个自然数，利用分治法实现归并分类。 输入格式: 第一行为自然数n，第二行开始为n个自然数。 输出格式: 输出n个自然数的归并分类结果。 输入样例1: 5 9 6 2 6 3 输出样例1: 在这里给出相应的输出。例如： 2 3 6 6 9

好的，以下是使用C语言实现的代码：

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

void merge(int arr[], int left[], int left_size, int right[], int right_size) {
    int i = 0, j = 0, k = 0;

    while (i < left_size && j < right_size) {
        if (left[i] < right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }

    while (i < left_size) {
        arr[k++] = left[i++];
    }

    while (j < right_size) {
        arr[k++] = right[j++];
    }
}

void merge_sort(int arr[], int size) {
    if (size <= 1) {
        return;
    }

    int mid = size / 2;
    int *left = (int *) malloc(mid * sizeof(int));
    int *right = (int *) malloc((size - mid) * sizeof(int));

    for (int i = 0; i < mid; i++) {
        left[i] = arr[i];
    }

    for (int j = mid; j < size; j++) {
        right[j - mid] = arr[j];
    }

    merge_sort(left, mid);
    merge_sort(right, size - mid);

    merge(arr, left, mid, right, size - mid);

    free(left);
    free(right);
}

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

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

    merge_sort(arr, n);

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

    return 0;
}

输入样例：

5
9 6 2 6 3

输出样例：

2 3 6 6 9