Sorting on STAR

This paper gives timing comparisons for three sorting algorithms written for the CDC STAR computer. One algorithm is Hoare's Quicksort, which is the fastest or nearly the fastest sorting algorithm for most computers. A second algorithm is a vector version of Quicksort that takes advantage of the STAR's vector operations. The third algorithm is an adaptation of Batcher's sorting algorithm, which makes especially good use of vector operations but has a complexity of N (log N)2 as compared to a complexity of N log N for the Quicksort algorithms. In spite of its worse complexity, Batcher's sorting algorithm is competitive with the serial version of Quicksort for vectors up to the largest that can be treated by STAR. Vector Quicksort outperforms the other two algorithms and is generally preferred. These results indicate that unusual instruction sets can introduce biases in program execution time that counter results predicted by worst-case asymptotic complexity analysis.     

归并方式的多线程快速排序算法

本文基于Java平台针对经典快速排序提出改进方案,使用归并的思想对快速排序作了多线程优化,并对单、多线程下的快速排序进行了对比测试和分析。结果表明,通过多线程优化,快速排序在双核主机上对5千万个随机整型数据进行排序的速度是单线程的1.6倍,说明了该优化方法的有效性。该方法思路直观、容易理解,宜作为多核技术教学案例。     

A stable quicksort

A sorting algorithm, called Stable Quicksort, is presented. the algorithm is comparable in speed with the Quicksort algorithm, but is stable. The experimental evidence presented support the theoretical evaluation of the performance of Stable Quicksort.     

External sorting: run formation revisited

External mergesort begins with a run formation phase creating the initial sorted runs. Run formation can be done by a load-sort-store algorithm or by replacement selection. A load-sort-store algorithm repeatedly fills available memory with input records, sorts them, and writes the result to a run file. Replacement selection produces longer runs than load-sort-store algorithms and completely overlaps sorting and I/O, but it has poor locality of reference resulting in frequent cache misses and the classical algorithm works only for fixed-length records. This paper introduces batched replacement selection: a cache-conscious version of replacement selection that works also for variable-length records. The new algorithm resembles AlphaSort in the sense that it creates small in-memory runs and merges them to form the output runs. Its performance is experimentally compared with three other run formation algorithms: classical replacement selection, Quicksort, and AlphaSort. The experiments show that batched replacement selection is considerably faster than classic replacement selection. For small records (average 100 bytes), CPU time was reduced by about 50 percent and elapsed time by 47-63 percent. It was also consistently faster than Quicksort, but it did not always outperform AlphaSort. Replacement selection produces fewer runs than Quicksort and AlphaSort. The experiments confirmed that this reduces the merge time whereas the effect on the overall sort time depends on the number of disks available.     

Bidirectional Conditional Insertion Sort algorithm; An efficient progress on the classical insertion sort

In this paper, we proposed a new efficient sorting algorithm based on insertion sort concept. The proposed algorithm is called Bidirectional Conditional Insertion Sort (BCIS). It is in-place sorting algorithm and it has remarkably efficient average case time complexity when compared with classical insertion sort (IS). By comparing our new proposed algorithm with the Quicksort algorithm, BCIS indicated faster average case time for relatively small size arrays up to 1500 elements. Furthermore, BCIS was observed to be faster than Quicksort within high rate of duplicated elements even for large size array.     

Exploiting partial order with Quicksort

The widely known Quicksort algorithm does not attempt to actively take advantage of partial order in sorting data. A simple change can be made to the Quicksort strategy to give a bestcase performance of n, for ordered data, with a smooth transition to O(n log n) for random data. This algorithm (Transort) matches the performance of Sedgewick's claimed best implementation of Quicksort for random data.     

应用于大数据的Trie树排序算法

针对在数据量动态增加的场景下现有的排序算法管理数据导致算法性能大大降低的问题,提出一种16-bit Trie树排序算法.借助邻居节点上存储的链节点指针完成排序,它不仅可以边构建边排序,且引入动态数组可以提高该算法的空间效率.仿真结果表明,传统Trie树支持数据动态更新,但通过遍历Trie树的方式完成排序耗时较多,快速排...     

A new external sorting algorithm with no additional disk space

This paper is concerned with an external sorting algorithm with no additional disk space. The proposed algorithm is a hybrid one that uses Quicksort and special merging process in two distinct phases. The algorithm excels in sorting a huge file, which is many times larger than the available memory of the computer. This algorithm creates no extra backup file for manipulating huge records. For this, the algorithm saves huge disk space, which is needed to hold the large file. Also our algorithm switches to special merging process after the first phase that uses Quicksort. This reduces the time complexity and makes the algorithm faster.     

一种非比较分段排序算法的研究

非比较分段排序（简称NCSS）算法是建立在模仿人类思想方式基础上的一种非比较排序算法，算法分析和实验结果都表明：NCSS算法的时间复杂度和待排序数据分布无关，为O（N），而附加存储空间极小，排序速率明显优于QuickSort,ProportionSplitSort，分段快速排序等算法，NCSS算法特别适合于数据最大的场合。     

Improving multikey Quicksort for sorting strings with many equal elements

Bentley and Sedgewick proposed multikey Quicksort with ‘split-end’ partitioning for sorting strings. But it can be slow in case of many equal elements because it adopted ‘split-end’ partitioning that moves equal elements to the ends and swaps back to the middle. We present ‘collect-center’ partitioning to improve multikey Quicksort in that case. It moves equal elements to the middle directly like the ‘Dutch National Flag Problem’ partitioning approach and it uses two inner loops like Bentley and McIlroy's. In case of many equal elements such as DNA sequences, HTML files, and English texts, multikey Quicksort with ‘collect-center’ partitioning is faster than multikey Quicksort with ‘split-end’ partitioning.     

一种实用的数值型伪Hash函数排序方法

本文给出一种具有实用价值的数值型伪Ｈａｓｈ函数排序方法。该方法通过尽量避免比较而直接计算定位的方式提高排序速度。测试结果表明：该算法的排序时间好于比较式排序的代表性算法Ｑｕｉｃｋｓｏｒｔ，Ｓｈｅｌｌｓｏｒｔ。与现有算法相比，该算法简洁，灵活，易于实现，适合于某些应用领域的特殊需求。     

Performance assessment of multithreaded quicksort algorithm on simultaneous multithreaded architecture

Sorting huge amounts of datasets have become essential in many computer applications, such as search engines, database and web-based applications, in order to improve searching performance. Moreover, due to the witnessed prevalence of the commercial Simultaneous Multithreaded architecture (SMT), parallel programming using multithreading becomes a dire need for efficiently using all available hardware resources for one application. In this paper, one of the efficient and quick algorithms, the Quicksort, is applied as a parallel multithreaded algorithm on SMT architecture, where virtual parallelization has been achieved using the POSIX threads (Pthreads) library. The proposed algorithm is evaluated and compared with its sequential counterpart. The obtained analytical and experimental results reveal that multithreading is a viable technique for implementing the parallel Quicksort algorithm efficiently on SMT architecture, where it has been shown both analytically and experimentally that the parallel multithreaded Quicksort algorithm outperforms the sequential Quicksort algorithm in terms of various performance metrics including; time complexity and speedup.     

Two simple and efficient algorithms for Jordan sorting and polygon cutting and clipping

This paper deals with the Jordan sorting problem: Given n intersection points of a Jordan curve with the x-axis in the order in which they occur along the curve, sort these points into the order in which they occur along the x-axis. The worst-case time complexity of this problem is θ(n). Unfortunately, the known O(n) time algorithms are too complicated, which causes that they are difficult to implement and slow for the inputs of sizes that are of practical interest. In this paper, two algorithms for Jordan sorting are presented. The first algorithm is extremely simple. Although its worst-case time complexity is O(nlogn), it is shown that the worst time is achieved only for special inputs. For most inputs, a better performance can be expected. Furthermore, an improved O(nlog logn) worst-case time algorithm is presented. For the input sequences of size from 4 to 10⁵, the algorithms are compared with Quicksort, with the algorithm based on splay trees and with the O(n) time algorithm proposed by Fung et al. The results show that our algorithms are faster. The relevant implementation details are given.     

The parallel quicksort algorithm part 2—simulation

This paper is the second of a two part series in which a general purpose sorting algorithm i.e. Quicksort is adapated for execution on an M.I.M.D. computer system. In this part, the parallel algorithm derived in Part 1 is simulated and qualitative agreement with the results from the run-time analysis was obtained.     

Introspective Sorting and Selection Algorithms

Quicksort is the preferred in-place sorting algorithm in many contexts, since its average computing time on uniformly distributed inputs is Θ(N log N), and it is in fact faster than most other sorting algorithms on most inputs. Its drawback is that its worst-case time bound is Θ(N²). Previous attempts to protect against the worst case by improving the way quicksort chooses pivot elements for partitioning have increased the average computing time too much – one might as well use heapsort, which has a Θ(N log N) worst-case time bound, but is on the average 2–5 times slower than quicksort. A similar dilemma exists with selection algorithms (for finding the i-th largest element) based on partitioning. This paper describes a simple solution to this dilemma: limit the depth of partitioning, and for subproblems that exceed the limit switch to another algorithm with a better worst-case bound. Using heapsort as the ‘stopper’ yields a sorting algorithm that is just as fast as quicksort in the average case, but also has an Θ(N log N) worst case time bound. For selection, a hybrid of Hoare's FIND algorithm, which is linear on average but quadratic in the worst case, and the Blum–Floyd–Pratt–Rivest–Tarjan algorithm is as fast as Hoare's algorithm in practice, yet has a linear worst-case time bound. Also discussed are issues of implementing the new algorithms as generic algorithms, and accurately measuring their performance in the framework of the C+:+ Standard Template Library. ©1997 by John Wiley & Sons, Ltd.     

基于数据分布特性的快速排序

文中提出了一种基于数据分析特性的快速排序算法，根据被排数据的分布行性，选择数据比较次数和数据移动次数较少的排序算法，当被排数据存在ｍ个有序序列时，其算法的时间复杂度为Ｏ（ｎｌｏｇ２ｍ）其中ｍ∈（１，ｃｆ√ｎ），ｃ为某一常数，其最佳性能为Ｏ（ｎ）。当ｍ≥ｃ（√ｎ）时，保持快速排序的最佳平均性能，使排序运行于较优状态下。     

Acceleration of sweep-line technique by employing smart quicksort

Quicksort is usually the best practical choice for sorting because it is, on average, remarkably efficient. Unfortunately, this popular algorithm has a significant drawback: the slowest performance is obtained in the simplest cases when input data are already initially sorted or only a slight perturbation occurs. In this paper, we propose a combination of quicksort and a new algorithm, which shows excellent time performance in sorting such crucial data arrays, and which is not much slower than quicksort in random cases. Our work was inspired by problems met when sorting polygon vertices in the sweep-line algorithms of computational geometry and, therefore, we have named the new algorithm ‘vertex sort’. It splits the input array into three sub-arrays. Two of them are already sorted, and the third one is handled iteratively. A simple test decides whether to continue recursively with vertex sort or to employ quicksort in the second iteration. In this way, we achieve a situation where the worst case time complexity does not exceed the running times of quicksort, but the simplest cases are handled much faster (in linear time) than random cases. We have named the combined algorithm ‘smart quicksort’ because of this desired property. In the last part of the paper, we prove its efficiency by employing it in a well-known sweep-line-based polygon triangulation algorithm.     

What is a Sorting Function?

What is a sorting function—not a sorting function for a given ordering relation, but a sorting function with nothing given?Formulating four basic properties of sorting algorithms as defining requirements, we arrive at intrinsic notions of sorting and stable sorting: A function is a sorting function if and only it is an intrinsically parametric permutation function. It is a stable sorting function if and only if it is an intrinsically stable permutation function.We show that ordering relations can be represented isomorphically as inequality tests, comparators and stable sorting functions, each with their own intrinsic characterizations, which in turn provide a basis for run-time monitoring of their expected I/O behaviors. The isomorphisms are parametrically polymorphically definable, which shows that it is sufficient to provide any one of the representations since the others are derivable without compromising data abstraction.Finally we point out that stable sorting functions as default representations of ordering relations have the advantage of permitting linear-time sorting algorithms; inequality tests forfeit this possibility.     

A parallel version of cook and Kim's algorithm for presorted lists

The Cook and Kim algorithm is a well known method for sorting presorted lists. This paper presents observations based on an implementation of the algorithm on a single processor. An extension of the algorithm to a tightly coupled multiprocessor will also be presented. The performance of the parallel version of the algorithm on presorted lists will be compared to that of a heavily used parallel sort algorithm for tightly coupled multiprocessors, Parallel Quicksort.     

The analysis of Quicksort programs

Summary The Quicksort sorting algorithm and its best variants are presented and analyzed. Results are derived which make it possible to obtain exact formulas describing the total expected running time of particular implementations on real computers of Quicksort and an improvement called the median-of-three modification. Detailed analysis of the effect of an implementation technique called loop unwrapping is presented. The paper is intended not only to present results of direct practical utility, but also to illustrate the intriguing mathematics which arises in the complete analysis of this important algorithm.This work was supported in part by the Fannie and John Hertz Foundation, and in part by the National Science Foundation Grants No. GJ-28074 and MC S75-23738