MergeSort

C语言实现归并排序
基本思想如下：将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。
综上可知，归并排序其实要做两件事情：
（1）“分解”——将序列每次折半划分；
（2）“合并”——将划分后的序列段两两合并后排序；
那么如何进行合并呢？
在每次合并过程中，都是对两个有序的序列段进行合并，然后排序。这两个有序序列段分别为R[low,mid],R[mid+1,high]。先将它们合并到一个局部的暂存数组R2中，合并完成后再将R2复制到R中。R[low,mid]称为第一段，R[mid+1,high]称为第二段，每次从两个段中取出一个记录进行关键字的比较，将较小者放入R2中。最后将各段中余下的部分直接复制到R2中。经过这样，R2已经是一个有序的序列，再将其复制回R中，一次合并排序就完成了。