归并排序是采用分治法的典型应用。 参考《数据结构与算法分析-Java语言描述》
归并排序其实要做两件事：
（1）“分解”——将序列每次折半划分。
（2）“合并”——合并两个已排序的表。
合并：对于两个输入数组A和B，一个输出数组C，以及3个计数器Actr、Bctr、Cctr，他们的初始置于对应数组的开始端。A[Actr]和B[Bctr]中较小的拷贝到C中的下一个位置，相关的计数器向前推进一步。当两个输入表有一个用完时，则将另一个表中剩余的部分拷贝到C中。
最坏运行时间O(nlogn)
原文：http://www.cnblogs.com/xiaolovewei/p/7570651.html