归并排序模板

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int temp[100];
int num=0;
void Merge(int a[],int left,int mid,int right){
  int i=left,j=mid+1,n=0,length=right-left;
  while(i<=mid && j<=right){ //这个是两个有序的数组，进行合并成为一个数组
    if (a[i]>a[j]){
        temp[n++]=a[j++];
        num+=mid-i+1;
    }else {
        temp[n++]=a[i++];
    }
  }
  if(i>mid){//把剩下的放进去
    while(j<=right){
        temp[n++]=a[j++];
    }
  }
  else{
    while(i<=mid){
        temp[n++]=a[i++];
    }
  }
  for(int k=0;k<=length;k++){
    a[left+k]=temp[k];
  }
}
void mergesort(int a[],int left,int right){
   if (left<right){
    int mid=(left+right)/2;
    mergesort(a,left,mid);
    mergesort(a,mid+1,right);
    Merge(a,left,mid,right);
   }
}
int main(){
  int a[100];
  int n;
  scanf("%d",&n);
  for (int i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  mergesort(a,0,n-1);
  for (int i=0;i<n;i++){
    printf("%d ",a[i]);
  }
  return 0;
}