Quicksort for Equal Keys
- 1 April 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-34 (4) , 362-367
- https://doi.org/10.1109/tc.1985.5009387
Abstract
When sorting a multiset of N elements with n ≪ N distinct values, considerable savings can be obtained from an algorithm which sorts in time O(N log n) rather than O(N log N). In a previous paper, two Quicksort derivatives operating on linked lists were introduced which are stable, i.e., maintain the relative order of equal keys, and which achieve the previously unattainable lower bound in partition exchange sorting. Here, six more algorithms are presented which are unstable but operate on arrays. One of the algorithms is also designed for a speedup on presorted input. The algorithms are analyzed and compared to potential contenders in multiset sorting.Keywords
This publication has 12 references indexed in Scilit:
- Smoothsort's behavior on presorted sequencesInformation Processing Letters, 1983
- Sorting a linked list with equal keysInformation Processing Letters, 1982
- Sci. Comput. ProgrammingScience of Computer Programming, 1982
- Smoothsort, an alternative for sorting in situScience of Computer Programming, 1982
- A stable quicksortSoftware: Practice and Experience, 1981
- The cyclic order property of vertices as an aid in scene analysisCommunications of the ACM, 1979
- Sorting presorted filesPublished by Springer Nature ,1979
- Implementing Quicksort programsCommunications of the ACM, 1978
- Quicksort with Equal KeysSIAM Journal on Computing, 1977
- QuicksortThe Computer Journal, 1962