什么是归并

把两个或多个已经有序的序列合并成一个

“2路”归并

即将两个有序序列合并
image.png

多路归并

把多个有序序列归并成一个
image.png
image.png

二路归并排序手算模拟

image.png
核心操作:把数组内两个有序的子序列归并为一个

代码实现

归并步骤

image.png

归并排序(递归)

image.png

算法效率分析

2路归并的“归并树”形态上就是一颗倒立的二叉树
image.png

时间复杂度

image.png

空间复杂度

image.png

稳定性

归并排序是稳定的

总结

image.png