归并排序
个人认为归并排序和快速排序有相似之处，都是从大数组一步一步化为小数组再分步解决。
归并排序的思想其实很简单，总共分为两步，分与治。
分指的就是将一个大数组一步一步变小，总体化小再化小，如下图本是长度为8的数组分为两个长度为4的数组再一步一步分下去直到8个数字。
核心代码
1 if(first<last) 2 { 3 int mid=(first+last)/2; 4 mergesort(a,first,mid,temp); //左边有序 5 mergesort(a,mid+1,last,temp); //右边有序 6 mergearray(a,first,mid,last,temp); //再将两个有序数组合并 7 } 8
治就是将小的数组排好序，再一步步整合为大的数组。
之所以要先不断分隔，是为了左右两侧内部要保证有序，才可以进行归并操作。
核心代码
1 while(i<=m&&j<=n) 2 { 3 if(a[i]<a[j]) 4 temp[k++]=a[i++]; 5 else 6 temp[k++]=a[j++]; 7 } 8 while(i<=m) 9 temp[k++]=a[i++]; 10 while(j<=n) 11 temp[k++]=a[j++]; 12 for(i=0;i<k;i++) 13 a[first+i]=temp[i];
/ 图源于 https://blog.csdn.net/qq_41900081/article/details/86776586
动态图
// 图源于 https://blog.csdn.net/qq_40907279/article/details/81607634
归并排序的时间复杂度为O(nlogn) ，因为递归（分）每次按照一半分区（八个变四个）。最重要的是该算法中最好、最坏和平均的时间性能都是O(nlogn)。
快速排序虽然时间复杂度为O(nlogn)但是有特殊情况。 相比较就是因为归并排序使用空间换时间。
完整代码
1 #include<stdio.h> 2 #include<stdlib.h> 3 long long int ans=0; 4 void memerge(long long int *s, int start, int end) 5 { 6 int mid=(start+end)/2; 7 if(start<end) 8 { 9 memerge(s,start,mid); 10 memerge(s,mid+1,end); 11 } 12 int n[65599]; 13 int i,j,k; 14 for(i=start,j=1,k=0;i<=mid&&mid+j<=end;) 15 { 16 if(s[i]>s[mid+j]) 17 { 18 ans+=(mid-i+1); 19 n[k++]=s[mid+j++]; 20 } 21 else 22 { 23 n[k++]=s[i++]; 24 } 25 } 26 while(i<=mid)n[k++]=s[i++]; 27 while(mid+j<=end)n[k++]=s[mid+j++]; 28 for(i=start,k=0;k<end-start+1;k++) 29 s[i+k]=n[k]; 30 } 31 32 int main() 33 { 34 int n,i,j; 35 long long int *s; 36 scanf("%d",&n); 37 s=(long long int *)malloc(sizeof(long long int)*n); 38 for(i=0;i<n;i++) 39 { 40 scanf("%lld",s+i); 41 } 42 memerge(s,0,n-1); 43 printf("%lld\n",ans); 44 ans=0; 45 }
归并排序还可以用在求逆序数中的题目，而快速排序则8太行。
原文：https://www.cnblogs.com/johnfllora/p/12231013.html