Article

Free access

New merge sorting techniques

Authors:

B. K. Betz,

W. C. CarterAuthors Info & Claims

ACM '59: Preprints of papers presented at the 14th national meeting of the Association for Computing Machinery

Pages 1 - 4

https://doi.org/10.1145/612201.612219

Published: 01 September 1959 Publication History

PDF eReader

Cited By

View all

Perez-Cerrolaza JAbella JKosmidis LCalderon ACazorla FFlores J(2022)GPU Devices for Safety-Critical Systems: A SurveyACM Computing Surveys10.1145/354952655:7(1-37)Online publication date: 15-Dec-2022
https://dl.acm.org/doi/10.1145/3549526
Sarsenbayeva ZVan Berkel NVelloso EGoncalves JKostakos V(2022)Methodological Standards in Accessibility Research on Motor Impairments: A SurveyACM Computing Surveys10.1145/354350955:7(1-35)Online publication date: 15-Dec-2022
https://dl.acm.org/doi/10.1145/3543509
Jacobson N(2000)Using on-computer exams to ensure beginning students' programming competencyACM SIGCSE Bulletin10.1145/369295.36932432:4(53-56)Online publication date: 1-Dec-2000
https://dl.acm.org/doi/10.1145/369295.369324
Show More Cited By

Recommendations

Strategies for stable merge sorting
SODA '19: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms

We introduce new stable natural merge sort algorithms, called 2-merge sort and α-merge sort. We prove upper and lower bounds for several merge sort algorithms, including Timsort, Shiver's sort, α-stack sorts, and our new 2-merge and α-merge sorts. The ...
A Multiway Merge Sorting Network

A multiway merge sorting network is presented, which generalizes the technique used in the odd-even merge sorting network. The merging network described here is composed of $m\ k$-way mergers and a combining network. It arranges $k$ ordered lists of ...
An Efficient Implementation of Batcher's Odd-Even Merge Algorithm and Its Application in Parallel Sorting Schemes

An algorithm is presented to merge two subfiles of size n/2 each, stored in the left and the right halves of a linearly connected processor array, in 3n/2 route steps and log n compare-exchange steps. This algorithm is extended to merge two horizontally ...

Comments

Information & Contributors

Information

Published In

ACM '59: Preprints of papers presented at the 14th national meeting of the Association for Computing Machinery

September 1959

278 pages

ISBN:9781450373647

DOI:10.1145/612201

Conference Chair:
Eric A. Weiss

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1959

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
201
Total Downloads

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

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Perez-Cerrolaza JAbella JKosmidis LCalderon ACazorla FFlores J(2022)GPU Devices for Safety-Critical Systems: A SurveyACM Computing Surveys10.1145/354952655:7(1-37)Online publication date: 15-Dec-2022
https://dl.acm.org/doi/10.1145/3549526
Sarsenbayeva ZVan Berkel NVelloso EGoncalves JKostakos V(2022)Methodological Standards in Accessibility Research on Motor Impairments: A SurveyACM Computing Surveys10.1145/354350955:7(1-35)Online publication date: 15-Dec-2022
https://dl.acm.org/doi/10.1145/3543509
Jacobson N(2000)Using on-computer exams to ensure beginning students' programming competencyACM SIGCSE Bulletin10.1145/369295.36932432:4(53-56)Online publication date: 1-Dec-2000
https://dl.acm.org/doi/10.1145/369295.369324
Pareja-Flores CVelázquez-Iturbide J(2000)Local versus comprehensive assignmentsACM SIGCSE Bulletin10.1145/369295.36932232:4(48-51)Online publication date: 1-Dec-2000
https://dl.acm.org/doi/10.1145/369295.369322
Reese D(2000)Using multiplayer games to teach interprocess communication mechanismsACM SIGCSE Bulletin10.1145/369295.36932132:4(45-47)Online publication date: 1-Dec-2000
https://dl.acm.org/doi/10.1145/369295.369321
Matos VGrasser R(2000)RELAX — the relational algebra pocket calculator projectACM SIGCSE Bulletin10.1145/369295.36932032:4(40-44)Online publication date: 1-Dec-2000
https://dl.acm.org/doi/10.1145/369295.369320
Sedgewick R(1980)EFFICIENT SORTING BY COMPUTER: AN INTRODUCTIONComputational Probability10.1016/B978-0-12-394680-5.50012-2(101-130)Online publication date: 1980
https://doi.org/10.1016/B978-0-12-394680-5.50012-2
Lozinskii L(1972)An analysis of external merge sorting techniquesCybernetics10.1007/BF010747504:1(21-28)Online publication date: 1972
https://doi.org/10.1007/BF01074750
Shell D(1971)Optimizing the polyphase sortCommunications of the ACM10.1145/362854.36288114:11(713-719)Online publication date: 1-Nov-1971
https://dl.acm.org/doi/10.1145/362854.362881
Gallaher L(1967)Algorithm 303: An adaptive quadrature procedure with random panel sizesCommunications of the ACM10.1145/363332.36340810:6(373-374)Online publication date: 1-Jun-1967
https://dl.acm.org/doi/10.1145/363332.363408
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Strategies for stable merge sorting

A Multiway Merge Sorting Network

An Efficient Implementation of Batcher's Odd-Even Merge Algorithm and Its Application in Parallel Sorting Schemes

Comments

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Other Metrics

Article Metrics

Other Metrics

Cited By

PDF

eReader

Login options

Full Access

Cited By

Recommendations

Strategies for stable merge sorting

A Multiway Merge Sorting Network

An Efficient Implementation of Batcher's Odd-Even Merge Algorithm and Its Application in Parallel Sorting Schemes

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Share

Share this Publication link

Share on social media

Affiliations