缫丝排序算法

文中提出一种改进的排序算法,弥补了快速排序在大规模下堆栈低效及合并排序在小规模下优势不明显的问题.算法扩展了合并排序思想,从一种特殊的蚕茧缫丝工艺得到启发,使用2～6个滚轴分离待排序列中的有序片段,在滚轴始末端扩展新数据,从而达到在合并操作前增加有序子序列长度的目的.理论推导表明,缫丝排序中的基本操作数量较合并排序减少4.75N,相当于将待排序列缩小至原有规模的1/4;效率测试实验表明,缫丝排序在各种规模下均能获得相比最快经典排序算法10％～15％的稳定优势,相比前人的改进排序算法具备相当的互补性,并能有效降低排序库函数自适应选择算法的实现复杂度.

ReelingSort: A New Algorithms in Cluster-Sorting

This paper proposes an improved universal internal sorting algorithm,which overcomes the low efficiency problem caused by using stacks in quick-sort when the input size is large and outperforms the bottom-up merge-sort when the input size is small.Inspired by a special reeling process in textile,this algorithm uses two to six "rollers" to separate the ordered segments and gradually grows these segments from their both ends in order to increase the length of the overall ordered sequence.It is proved theoretically that ReelingSort costs 4.75N less than bottom-up merge-sort given the input size of N,which is equivalent to 25% of the original time complexity.Efficiency evaluation experiments demonstrate that,ReelingSort outperforms the state-of-the-art sorting algorithm over 10% no matter how large the input size is.Furthermore,it can be regarded as necessary complementary to predecessor’s work,and effectively reduce design complexity of the self-adapting sorting such as python’s scheme.