Name
Abstract | ||
|---|---|---|
The complexity of merging two sorted sequences into one is linear in the worst case as well as in the average case. There are, however, instances for which a sublinear number of comparisons is sufficient. We consider the problem of measuring and exploiting such instance easiness. The merging algorithm presented, Adaptmerge, is shown to adapt optimally to different kinds of measures of instance easiness. In the sorting problem the concept of instance easiness has received a lot of attention, and it is interpreted by a measure of presortedness. We apply Adaptmerge in the already adaptive sorting algorithm Natural Mergesort. The resulting algorithm, Adaptive Mergesort, optimally adapts to several, known and new, measures of presortedness. We also prove some interesting results concerning the relation between measures of presortedness proposed in the literature. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1007/BF01190160 | Algorithmica |
Keywords | Field | DocType |
Merging,Sorting,Instance easiness,Measures | Sublinear function,Merge sort,Theoretical computer science,Merge (version control),Mathematics | Journal |
Volume | Issue | ISSN |
9 | 6 | 0178-4617 |
Citations | PageRank | References |
16 | 2.75 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Svante Carlsson | 1 | 764 | 90.17 |
| Christos Levcopoulos | 2 | 759 | 84.69 |
| Ola Petersson | 3 | 239 | 31.95 |