请用C语言实现输入格式: 第一行为自然数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_sort(int *arr, int l, int r);
void merge(int *arr, int l, int mid, int r);

int main() {
    int n;
    scanf("%d", &n);
    int *arr = (int *) malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    merge_sort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    free(arr);
    return 0;
}

void merge_sort(int *arr, int l, int r) {
    if (l >= r) {
        return;
    }
    int mid = (l + r) / 2;
    merge_sort(arr, l, mid);
    merge_sort(arr, mid + 1, r);
    merge(arr, l, mid, r);
}

void merge(int *arr, int l, int mid, int r) {
    int i = l;
    int j = mid + 1;
    int k = 0;
    int *tmp = (int *) malloc((r - l + 1) * sizeof(int));
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    while (j <= r) {
        tmp[k++] = arr[j++];
    }
    for (int p = 0; p < k; p++) {
        arr[l + p] = tmp[p];
    }
    free(tmp);
}

输入样例：

5
9 6 2 6 3

输出样例：

2 3 6 6 9