链表递增归并排序算法

摘要：

归并排序是一种稳定,高效的排序算法.归并排序算法一般是用顺序存储结构实现的.如Sun公司JDK中Jwa Collection库中对数组、List的排序.使用顺序存储结构实现归并排序需要空间复杂度为O(n)的辅助存储空间,对于链表来说,还需要转换为顺序存储结构,所以共需要2n的辅助存储空间.本文提出一种链表非递归归并排序算法,可以对链表进行原地(In Place)排序,只需要O(logn)的辅助存储空间,时间复杂度不变.

关键词：链表、归并、排序、算法

分类号：TP312(计算技术、计算机技术)

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

页数：共4页

页码：9-12