AN EFFICIENT MULTIWAY MERGING ALGORITHM

Authors
ZHAO LJ LIU ZY GAO QS
Citation
Lj. Zhao et al., AN EFFICIENT MULTIWAY MERGING ALGORITHM, SCI CHINA E, 41(5), 1998, pp. 543-551
Citations number
10
Categorie Soggetti
Engineering,"Material Science
Journal title
SCIENCE IN CHINA SERIES E-TECHNOLOGICAL SCIENCES
ISSN journal
20950624 → ACNP
Volume
41
Issue
5
Year of publication
1998
Pages
543 - 551
Database
ISI
SICI code
2095-0624(1998)41:5<543:AEMMA>2.0.ZU;2-T
Abstract
Most traditional merging algorithms and merging-based sorting algorith ms are based on 2-sorters. A new k-way merging algorithm is proposed. The aim of this algorithm is to merge k sorted lists, with m keys of e ach, into one, where k can be any integer. The merging process uses on ly k sorters instead of 2 sorters. Thus, K-sorters is the primary oper ation of our algorithm. The time needed to merge k sorted lists is (21 + ([log (m/k)])t(k), where t(k) is the time to sort k keys.