数据结构合集 - 归并排序(非递归与递归算法过程, 效率分析, 稳定性分析)

なみだぐも:
感谢，讲得太好了，看10分钟视频的收获顶我啃40分钟的王道书，最近攒的硬币都献给up[打call]

【回复】谢谢支持[给心心][给心心][给心心]
A4的钉子:
递归实现的归并排序归并将会是比较平衡的，每次归并的左右两个子数组长度差距不会超过1 而简单非递归实现的归并排序在面对长度非2^n序列时容易造成很长的序列归并很短的序列的情况，这种情况归并效率会偏低，特别是普通的归并算法 归并算法优化可以用双向归并，在实现确定一边比另一边短时可以只取一个分支，双向归并只需要被归并的区间中短的那一个区间长度的辅助空间，虽然复杂度还是那样但实际使用的辅助空间直接可以降低一半 常用优化还有常见的小区间使用插入排序、对于归并头尾先跳过无需归并的区间（也就是归并前后并不需要改变的区间）、还有在持续遇到元素一直大于其中一个子区间的元素时可以采取更优化的查找方式去查找这个区间末尾并一次放入 timsort是一种基于非递归归并排序的算法，其优势在于尽量减少比较次数，且使用的辅助空间通常非常少，而且对于部分有序的序列非常高效。通过维护一个归并栈从而达到收集有序序列来归并的情况下能够尽量避免不平衡归并 而基于归并思路的算法还有一种排序网络，这类算法通常适合大批量并行排序，因为它们的比较结果并不影响比较位置，并且顺序不相关，这种特性使其非常适合并行设计。例如双调排序网络和奇偶排序网络

【回复】3：22都[doge]，一个字就能猜出你是哪的
小龙喜欢看电视:
等我上岸，一定请你洗脚，速更新剩下的