图示
算法描述
把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列
申请空间，使其大小为两个已经排好序的数组的长度之和
把两个有序的数组通过比较桉顺序放到申请的空间中
把在申请空间上存放的元素复制到原数组相应的位置上
参考代码
测试
View Code
复杂度
空间复杂度：O(n)
时间复杂度： 最好 最坏 平均 统统O(nlogn)
稳定性
稳定
应用
数组中的逆序对。例如｛7，5，6，4｝的逆序对有（7，5）（7，6）（7，4）（5，4）（6，4）总共5个
思路
其实就是归并排序中，两个数字交换的次数 + 归并有序数组时后一个数组元素大于前一个数字元素的个数之和。
数组
链表
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3644064.html，如需转载请自行联系原作者