分段有序归并排序算法

摘要

任一数据序列都是分段有序的。基于这一特点,本文提出了分段有序归并排序算法。其最优时间复杂性为 O(n),空间复杂性为 O(1)。最坏情况下的比较次数少于 nlogn+0.057n,小于快速排序算法的平均比较次数,是同类算法的最优上界。