归并排序

基本原理

将两个有序数组合并为一个有序数组
当两个数组均有序时，可以使用快慢指针的方法，只需O(n)的时间复杂度
归并排序与快速排序对比：
快速排序先将大数组粗排，进而分成多个小数组
归并排序不断地将小数组合并为大数组

算法改进

Tim Sort

参考

白话经典算法系列之五 归并排序的实现

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 数据结构与算法--归并排序
    数据结构与算法--归并排序 归并排序 归并排序基于一种称为“归并”的简单操作。比如考试可能会分年级排名和班级排名，...
    sunhaiyu阅读 4,406评论 0赞 6
  • 算法笔记－排序02:归并排序,快速排序
    思路 归并排序的思想是先将数组分散为小数组分别排序，然后将结果归并起来。 原地归并的抽象方法 将两个已经排序好的数...
    不可思议的Mark阅读 9,517评论 12赞 31
  • Swift算法－归并排序Merge Sort
    声明：算法和数据结构的文章均是作者从github上翻译过来，为方便大家阅读。如果英语阅读能力强的朋友，可以直接到s...
    UnsanYL阅读 5,511评论 0赞 2
  • 归并排序及其优化
    Q：什么是归并排序？A：它是建立在归并操作上的一种有效的排序算法；是采用分治法的一个非常典型的应用；是一种稳定的 ...
    TinyDolphin阅读 8,072评论 5赞 4
  • 归并排序
    归并排序 所谓归并，就是将两个或两个以上的有序表合并成一个新的有序表。如下图所示，有两个已经排好序的有序表A[1]...
    JackChen1024阅读 6,919评论 0赞 4