Perfectly overlapped merging and sorting on a two-way linear array

✍ Scribed by Yen-Chun Lin

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 475 KB
• Volume: 60
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(96)00157-3

✦ Synopsis

We present a perfectly overlapped merging algorithm, which can require almost only input time to perform merge sorting on a linear array of processors. The optimal merge order that minimizes the merge sorting time is obtained in constant time. The merging algorithm and a previously proposed runs-generation algorithm can serve for sorting a very large file; the time complexity of the resulting algorithm is optimal under the hardware condition.