分段有序归并排序算法
- 出版年：1992
- 作者：何奉道
- 单位1：计算机科学与工程系
- 语种：中文
- 作者关键词：分段有序；排序；算法分析
- 起始页：41
- 总页数：6
- 刊名：西南交通大学学报
- 是否内版：否
- 刊频：双月刊
- 创刊时间：1954
- 主办单位：西南交通大学
- 主编：路湛沁
- 地址：成都市九里堤
- 邮编：610031
- 期：5
- 期刊索取号：P806.6 210
摘要
任一数据序列都是分段有序的。基于这一特点，本文提出了分段有序归并排序算法。其最优时间复杂性为O（n），空间复杂性为O（1）。最坏情况下的比较次数少于nlogn+0.057n，小于快速排序算法的平均比较次数，是同类算法的最优上界。