Improved Divide/Sort/Merge Sorting Networks

descriptionPublicationkeyboard_double_arrow_right Article 01 Sep 1975 English Publisher:Society for Industrial & Applied Mathematics (SIAM)Journal:SIAM Journal on Computing, volume 4, pages 264-270 (issn: 0097-5397, eissn: 1095-7111,

Copyright policy )

Authors: Robert L. (Scot) Drysdale III; Frank H. Young;

doi: 10.1137/0204022

Improved Divide/Sort/Merge Sorting Networks

- Summary
- Subjects
- Metrics

Abstract

This paper develops sorting networks using the divide/sort/merge strategy. These networks require \[ (0.25)N( \log _2 N )^2 - (0.386)N( \log _2 N ) + O(N) \] comparison-interchanges to sort a list of length N. This is an improvement of order $N(\log _2 N)$ over the best networks previously reported. (Using different methods, Van Voorhis [8] has improved upon these results.)

Keywords

Analysis of algorithms and problem complexity, Deterministic network models in operations research, Algorithms in computer science

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	10
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average