给定n个自然数，利用分治法实现归并分类，第一行为自然数n，第二行开始为n个自然数。c++实现

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

void merge_sort(int arr[], int left, int right); // 归并排序函数
void merge(int arr[], int left, int mid, int 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, 0, n-1); // 归并排序
for(int i = 0; i < n; i++){
printf("%d ", arr[i]); // 输出排序后的自然数
}
printf("\n");
return 0;
}

void merge_sort(int arr[], int left, int right){
if(left >= right) return; // 当子序列长度为1时结束递归
int mid = (left + right) / 2; // 取得中间位置
merge_sort(arr, left, mid); // 对左半边进行归并排序
merge_sort(arr, mid+1, right); // 对右半边进行归并排序
merge(arr, left, mid, right); // 将左右两半归并
}

void merge(int arr[], int left, int mid, int right){
int len = right - left + 1; // 计算子序列长度
int temp[len];
int i = left, j = mid+1, k = 0;
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(int p = 0; p < len; p++){
arr[left+p] = temp[p];
}
}