DocumentCode :
3321267
Title :
k-way merging and k-ary sorts
Author :
Greene, William A.
Author_Institution :
Dept. of Comput. Sci., New Orleans Univ., LA, USA
fYear :
1991
fDate :
3-5 Apr 1991
Firstpage :
197
Abstract :
A divide-and-conquer algorithm is given for merging k sorted lists, namely, recursively merge the first [k/2] lists, do likewise for the last [k/2] lists, then merge the two results. The author gets a tight bound for the expense of the worst case behavior of this merge. He shows the algorithm is cheapest among all similar divide-and-conquer approaches to k-way merging. He computes the expense of the k-ary sort; sometimes its expense is identical to that of the binary sort
Keywords :
list processing; merging; sorting; binary sort; divide-and-conquer algorithm; k-ary sort; k-way merging; merge; sorted lists; tight bound; worst case behavior; Computational efficiency; Computer science; Costs; Merging; Partitioning algorithms;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Applied Computing, 1991., [Proceedings of the 1991] Symposium on
Conference_Location :
Kansas City, MO
Print_ISBN :
0-8186-2136-2
Type :
conf
DOI :
10.1109/SOAC.1991.143874
Filename :
143874
Link To Document :
بازگشت