归并排序

归并排序

我终于看了归并排序了！！！其实我很久之前就准备把瑞士轮给做了，但是，我发现用STL里的sort过不了过后我就没再管它了，今天又看到了这道题，我还是决定看一看神奇的归并排序。

由于不喜欢看好多好多字，我们先放一张图（简单易懂）

我当时看到这图过后就恍pang然ran大da悟wu了，突然就懂了它的基本思想：归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。（感谢百度百科）（说人话就是采用一个分治的思想，然后在分成的每一小段<就先两个两个比，再四个四个比…>内进行排序，因为每一段都是有序的，在后来的每一步合并操作之中就都很方便了，只需要考虑四种情况<马上会在代码里面提到>,最后的最后，将它们合并成一个整体的操作）

所以代码怎么实现？因为我没想出来，就去网上看了看其他大神写的模版，然后我又突然就懂了（什么，又懂了？）

首先我们从main函数开始倒着往回推

1 int main(){
2     int n,a[10005];
3     cin>>n;
4     for(int i=0;i<n;i++) cin>>a[i];
5     mergesort(a,0,n);
6     for(int i=0;i<n;i++) cout<<a[i];
7     return 0;
8 }