A MULTIWAY MERGE SORTING NETWORK

Authors
LEE DL BATCHER KE
Citation
Dl. Lee et Ke. Batcher, A MULTIWAY MERGE SORTING NETWORK, IEEE transactions on parallel and distributed systems, 6(2), 1995, pp. 211-215
Citations number
3
Categorie Soggetti
System Science","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
Journal title
IEEE transactions on parallel and distributed systems → ACNP
ISSN journal
10459219
Volume
6
Issue
2
Year of publication
1995
Pages
211 - 215
Database
ISI
SICI code
1045-9219(1995)6:2<211:AMMSN>2.0.ZU;2-U
Abstract
A multiway merge sorting network is presented, which generalizes the t echnique used in the odd-even merge sorting network. The merging netwo rk described here is composed of m k-way mergers and a combining netwo rk. It arranges k ordered lists of length n each into one ordered list s in T(k) + inverted left perpendicularlog(m) ninverted right perpendi cular inverted left perpendicularlog2 kinverted right perpendicular in verted left perpendicularlog2 minverted right perpendicular steps, whe re T(k) is the number of steps needed to sort k keys in order; and k a nd m are any integers no longer restricted to 2.