论文标题
赫斯基索特
Huskysort
论文作者
论文摘要
关于分类主题的许多丰富文献都集中在最小化比较和/或交换/副本的数量上。但是，对于分类算法的性能，更合适的码数基于所需的数组访问的总数（“工作”）。对于基于分裂和构成（包括该主题上的迭代变化）的一种，我们可以将工作分为线性，即$ \ textbf {o}（n）$，工作和线性线性，即$ \ textbf {o} o}（o}（o}（n log n log n）$，工作。将工作从线性阶段移动到线性相的算法可能能够减少数组访问的总数，并间接地处理时间。本文介绍了一种分类方法，该方法通过替换廉价的比较来尽可能地减少线性阶段中昂贵的比较数量。在Java中，这两个系统是双轴QuickSort（用于原始词）和Timsort的对象。我们证明，这两种算法的组合可以比单独使用的算法要快得多，而对于任何算法来说，比较昂贵的对象类型。我们称这种改进的分类算法Huskysort。
Much of the copious literature on the subject of sorting has concentrated on minimizing the number of comparisons and/or exchanges/copies. However, a more appropriate yardstick for the performance of sorting algorithms is based on the total number of array accesses that are required (the "work"). For a sort that is based on divide-and-conquer (including iterative variations on that theme), we can divide the work into linear, i.e. $\textbf{O}(N)$, work and linearithmic, i.e. $\textbf{O}(N log N)$, work. An algorithm that moves work from the linearithmic phase to the linear phase may be able to reduce the total number of array accesses and, indirectly, processing time. This paper describes an approach to sorting which reduces the number of expensive comparisons in the linearithmic phase as much as possible by substituting inexpensive comparisons. In Java, the two system sorts are dual-pivot quicksort (for primitives) and Timsort for objects. We demonstrate that a combination of these two algorithms can run significantly faster than either algorithm alone for the types of objects which are expensive to compare. We call this improved sorting algorithm Huskysort.
