用c++写一个归并排序

好的，以下是用C语言实现归并排序的代码：

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

void merge(int arr[], int left, int mid, int right) {
  int n1 = mid - left + 1;
  int n2 = right - mid;
  
  int left_arr[n1], right_arr[n2];
  
  for (int i = 0; i < n1; i++) {
    left_arr[i] = arr[left + i];
  }
  
  for (int j = 0; j < n2; j++) {
    right_arr[j] = arr[mid + 1 + j];
  }
  
  int i = 0, j = 0, k = left;
  
  while (i < n1 && j < n2) {
    if (left_arr[i] <= right_arr[j]) {
      arr[k] = left_arr[i];
      i++;
    } else {
      arr[k] = right_arr[j];
      j++;
    }
    k++;
  }
  
  while (i < n1) {
    arr[k] = left_arr[i];
    i++;
    k++;
  }
  
  while (j < n2) {
    arr[k] = right_arr[j];
    j++;
    k++;
  }
}

void merge_sort(int arr[], int left, int right) {
  if (left < right) {
    int mid = left + (right - left) / 2;
    
    merge_sort(arr, left, mid);
    merge_sort(arr, mid + 1, right);
    
    merge(arr, left, mid, right);
  }
}

int main() {
  int n;
  printf("输入数组长度：");
  scanf("%d", &n);
    
  int arr[n];
  
  printf("输入数组：\n");
  for (int i = 0; i < n; ++i) {
    scanf("%d", &arr[i]);
  }
  
  merge_sort(arr, 0, n - 1);
  
  printf("排序后的数组：\n");
  
  for (int i = 0; i < n; ++i) {
    printf("%d ", arr[i]);
  }
  printf("\n");
  
  return 0;
}

这段代码实现了归并排序的算法。它首先将数组分为两半，然后分别对左半部分和右半部分进行排序，最后将两个有序的部分归并起来。归并过程中，它会比较左半部分和右半部分中的元素，然后将较小的元素先放入新数组中，并将指针向后移动，直到其中一个数组排序完成，然后将剩余的元素全部放入新数组中。

使用该算法进行排序的时间复杂度为O(nlogn)，空间复杂度为O(n)，其中n是排序的数组长度。