article

Engineering a sort function

Authors:

Jon L. Bentley,

M. Douglas McIlroyAuthors Info & Claims

Software—Practice & Experience, Volume 23, Issue 11

Pages 1249 - 1265

https://doi.org/10.1002/spe.4380231105

Published: 01 November 1993 Publication History

Abstract

No abstract available.

Cited By

View all

Dai YChen C(2024)Sparsity-Exploiting Distributed Projections onto a SimplexINFORMS Journal on Computing10.1287/ijoc.2022.032836:3(820-835)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1287/ijoc.2022.0328
Shiplu ARahman MWatanobe Y(2023)LSA: A Novel State-Of-The-Art Sorting Algorithm for Efficient Arrangement of Large DataProceedings of the 2023 4th Asia Service Sciences and Software Engineering Conference10.1145/3634814.3634829(105-111)Online publication date: 27-Oct-2023
https://dl.acm.org/doi/10.1145/3634814.3634829
Draz HElashker NMahmoud M(2023)Optimized Algorithms and Hardware Implementation of Median Filter for Image ProcessingCircuits, Systems, and Signal Processing10.1007/s00034-023-02370-x42:9(5545-5558)Online publication date: 17-Apr-2023
https://dl.acm.org/doi/10.1007/s00034-023-02370-x
Show More Cited By

Index Terms

Engineering a sort function
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Procedures, functions and subroutines
      2. Language types
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Sorting and searching

Recommendations

Building a new sort function for a C library

Up to now, the most efficient sort function for a C library was a variant of Hoare's Quicksort (qsort, for short), which was proposed by Bentley and Mcllroy in the early 1990s. Here we call this library function BM qsort. This paper introduces a library ...
K-Way Bitonic Sort

The k-way bitonic sort algorithm, a generalization of K.E. Batcher's bitonic sort algorithm (1968), is presented. This variation of the algorithm is based on a k-way decomposition instead of a two-way decomposition. It is proven that Batcher's bitonic ...
Formal engineering of the bitonic sort using PVS
IW-FM'98: Proceedings of the 2nd Irish conference on Formal Methods

In this paper, we present a proof that the bitonic sort is sound using PVS, a powerful specification and verification environment. First, we briefly introduce this well-known parallel sort. It is based on bitonic lists whose relevant properties can be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Software Volume 23, Issue 11

Nov. 1993

108 pages

ISSN:0038-0644

EISSN:1097-024X

Editors:
J. A. Campbell
Univ. College London, London, UK
,
D. E. Comer
Purdue Univ., West Lafayette, IN

Issue’s Table of Contents

Publisher

John Wiley & Sons, Inc.

United States

Publication History

Published: 01 November 1993

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

59
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dai YChen C(2024)Sparsity-Exploiting Distributed Projections onto a SimplexINFORMS Journal on Computing10.1287/ijoc.2022.032836:3(820-835)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1287/ijoc.2022.0328
Shiplu ARahman MWatanobe Y(2023)LSA: A Novel State-Of-The-Art Sorting Algorithm for Efficient Arrangement of Large DataProceedings of the 2023 4th Asia Service Sciences and Software Engineering Conference10.1145/3634814.3634829(105-111)Online publication date: 27-Oct-2023
https://dl.acm.org/doi/10.1145/3634814.3634829
Draz HElashker NMahmoud M(2023)Optimized Algorithms and Hardware Implementation of Median Filter for Image ProcessingCircuits, Systems, and Signal Processing10.1007/s00034-023-02370-x42:9(5545-5558)Online publication date: 17-Apr-2023
https://dl.acm.org/doi/10.1007/s00034-023-02370-x
Mahmud SHaque SChoudhury NOgden CGamess E(2022)Improving counting sort algorithm via data localityProceedings of the 2022 ACM Southeast Conference10.1145/3476883.3520203(211-214)Online publication date: 18-Apr-2022
https://dl.acm.org/doi/10.1145/3476883.3520203
Shao WLi JRen JZhang RWang XLuo P(2020)SSN: Learning Sparse Switchable Normalization via SparsestMaxInternational Journal of Computer Vision10.1007/s11263-019-01269-y128:8-9(2107-2125)Online publication date: 1-Sep-2020
https://dl.acm.org/doi/10.1007/s11263-019-01269-y
Lammich P(2020)Efficient Verified Implementation of Introsort and PdqsortAutomated Reasoning10.1007/978-3-030-51054-1_18(307-323)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.1007/978-3-030-51054-1_18
Li SLi HLiang XChen JGiem EOuyang KZhao KDi SCappello FChen ZTaufer MBalaji PPeña A(2019)FT-iSortProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3295500.3356195(1-17)Online publication date: 17-Nov-2019
https://dl.acm.org/doi/10.1145/3295500.3356195
Kotthoff LFréchette AMichalak TRahwan THoos HLeyton-Brown K(2018)Quantifying algorithmic improvements over timeProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304652.3304728(5165-5171)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304652.3304728
Mohammed AAmrahov aelebi F(2017)Bidirectional Conditional Insertion Sort algorithm; An efficient progress on the classical insertion sortFuture Generation Computer Systems10.1016/j.future.2017.01.03471:C(102-112)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1016/j.future.2017.01.034
Nazir AAlam MMalik SAkhunzada ACheema MKhan MZiang YKhan TKhan A(2017)A high-level domain-specific language for SIEM (design, development and formal verification)Cluster Computing10.1007/s10586-017-0819-220:3(2423-2437)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s10586-017-0819-2
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations

Building a new sort function for a C library

K-Way Bitonic Sort

Formal engineering of the bitonic sort using PVS

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations