Improved Divide/Sort/Merge Sorting Networks

Robert L. Scot Drysdale, Frank H. Young

SIAM Journal on Computing · 1975 · 13 citations · 1 references

Concepts

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.)

References

1