|
|||||
|
|
A Tree-based Mergesort |
|
| Authors: | Alistair Moffat Ola Petersson Nicholas C Wormald |
| Affiliation: | Department of Computer Science, The University of Melbourne, Parkville 3052, Australia (e-mail: alistair@cs.mu.oz.au), AU Department of Computer Science, Lund University, Box 118, S–221 00 Lund, Sweden; and Department of Mathematics, Statistics, and Computer Science, V?xj? University, S–351 95 V?xj?, Sweden (e-mail: ola@dna.lth.se), SE Department of Mathematics, The University of Melbourne, Parkville 3052, Australia (e-mail: N.Wormald@ms.unimelb.edu.au), AU |
| Abstract: | We demonstrate that if standard Mergesort is implemented using finger search trees instead of arrays it optimally adapts to a set of measures of presortedness not fulfilled by any other algorithm. Received: 7 October 1993 / 18 July 1996 |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |