Sloping-and-shaking - Multiway merging and sorting

	Sloping-and-shaking - Multiway merging and sorting
	Gao, QS; Liu, ZY
	1997-06-01
发表期刊	SCIENCE IN CHINA SERIES E-TECHNOLOGICAL SCIENCES
ISSN	1006-9321
卷号	40 期号:3 页码:225-234
摘要	Most traditional merging and merging-based sorting algorithms are based on 2 sorters or 2 comparators. A new merging technique is developed, namely sloping-and-shaking multiway merging, and a corresponding multiway sorting method based only on k-sorters is proposed. The sloping-and-shaking merging algorithm merges k sorted lists into one, where k can be any prime number. The merging process is not a series of recursive applications of 2-way merging. It sorts the keys on the m x k plane in vertical and horizontal directions, then along sloping lines with various slope rates step by step. Only k-sorters are needed in the merging or sorting process. The time needed to merge k sorted lists, with m of each, is (k + inverted right perpendicular log(2)(m/k) inverted left perpendicular)t(k), and the time for sorting N keys is (1 + (p - 1)k + 1/2(p - 1)(p - 2) inverted right perpendicular log(2)k inverted left perpendicular)t(k), where p = log(k)N, and t(k) is the time to sort k keys. The proposed algorithms can be implemented either by hardwared sorting networks, or on general purpose parallel and vector machines. The traditional odd-even merging can be viewed as a special case of the multiway merging proposed (when k is 2). While theoretically the proposed algorithms provide a new understanding of parallel merging and sorting processes, they may be used in practice to construct sorting circuits faster than 2-sorter based sorting methods.
关键词	parallel processing merging sorting algorithms time complexity
收录类别	SCI
语种	英语
WOS研究方向	Engineering ; Materials Science
WOS类目	Engineering, Multidisciplinary ; Materials Science, Multidisciplinary
WOS记录号	WOS:A1997XC20000001
出版者	SCIENCE CHINA PRESS
引用统计	被引频次：5[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/5464
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Gao, QS
作者单位	CHINESE ACAD SCI,COMP TECHNOL INST,BEIJING 100080,PEOPLES R CHINA
推荐引用方式 GB/T 7714	Gao, QS,Liu, ZY. Sloping-and-shaking - Multiway merging and sorting[J]. SCIENCE IN CHINA SERIES E-TECHNOLOGICAL SCIENCES,1997,40(3):225-234.
APA	Gao, QS,&Liu, ZY.(1997).Sloping-and-shaking - Multiway merging and sorting.SCIENCE IN CHINA SERIES E-TECHNOLOGICAL SCIENCES,40(3),225-234.
MLA	Gao, QS,et al."Sloping-and-shaking - Multiway merging and sorting".SCIENCE IN CHINA SERIES E-TECHNOLOGICAL SCIENCES 40.3(1997):225-234.