Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A simple linear-time algorithm for in situ merging
Mannila H., Ukkonen E. Information Processing Letters18 (4):203-208,1984.Type:Article
Date Reviewed: Feb 1 1985

This paper discusses a way to merge two sorted files in place and in linear time by dividing one file into a number (O(:9IN)) of equal parts, splitting the second file into matching parts, and resequencing them inthe order A1, B1, A2, B2, .9T.9T. before finally merging them. The need for an additional workspace is avoided by using the back and then the front section of the files as workspaces (which require resorting in place as a final step.

Reviewer:  John C. McPherson Review #: CR108806
Bookmark and Share
 
Sorting And Searching (F.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Sorting And Searching": Date
Binary search trees of almost optimal height
Anderson A., Icking C., Klein R., Ottmann T. (ed) Acta Informatica 28(2): 165-178, 1990. Type: Article
May 1 1992
More nearly optimal algorithms for unbounded searching, part II
Reingold E., Shen X. SIAM Journal on Computing 20(1): 184-208, 1991. Type: Article
Apr 1 1992
An upper bound for the speedup of parallel best-bound branch-and-bound algorithm
Quinn M., Deo N. BIT 26(1): 35-43, 1986. Type: Article
Nov 1 1987
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy