深度优先稳定原地归并排序的高效算法

摘要：

基于分治策略,使用深度优先的方法,提出了一种用于线性表的稳定原地归并排序算法,其时间复杂度为O(n lb n),辅助空间复杂度为O(1),递归栈空间复杂度为O(lb n),同时进行了算法分析和实验测试.实验结果表明,该算法效率较STL中的稳定原地归并排序算法有67.51％的提升,解决了稳定排序算法中要么时间复杂度高要么空间复杂度高的问题.

关键词：归并排序、原地排序、稳定排序、分治策略、深度优先

所属期刊栏目：33

分类号：TP311.12(计算技术、计算机技术)

在线出版日期：2013-05-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1039-1042,1060