Demo Data from EDBT 2026 / reviewers in the wild / expert
Mai Thanh
dblp:16/2680
· DBLP profile ↗
1ranked-venue papers
0as first author
0since 2021 · last 1989
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Applied, interdisciplinary, general and emerging computing · 1
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
1 paper |
Algorithms and data structures · 75% Computational complexity · 25% |
Topics — the 4 heaviest of 4, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Algorithms and data structures › sequence algorithms › sorting
comparison sorting |
0.0 | 1 | 1989 | Optimum combinations of sorting and merging · J. ACM 1989 |
Computational complexity
lower bounds |
0.0 | 1 | 1989 | Optimum combinations of sorting and merging · J. ACM 1989 |
Algorithms and data structures › sorting and merging
merging |
0.0 | 1 | 1989 | Optimum combinations of sorting and merging · J. ACM 1989 |
Algorithms and data structures
sorting and merging |
0.0 | 1 | 1989 | Optimum combinations of sorting and merging · J. ACM 1989 |
Methods — techniques the papers use, named apart from their topics
sort-merge sequence optimization · 0.0asymptotic analysis · 0.0
| Year | Publication | Venue | Position |
|---|---|---|---|
| 1989 | Optimum combinations of sorting and mergingabstractIn 1979, G. K. Manacher showed that the Ford-Johnson sorting algorithm [FJA], acting on t real numbers, can be beaten for an infinite set of values t . These values form a partial cover of constant density not close to 1 over an initial sequence of each band running from u k = ⌊(4/3)2 k ⌋ to u k +l - 1. This early result depended on showing that the Hwang-Lin merging algorithm [HLA], merging m elements with n , m ≠ n , could be surpassed by cm comparisons, where c is an arbitrary small positive constant. In this paper, it is shown that the FJA can be beaten for a set of integers of asymptotic density 1 under the greatly weakened assumption that the HLA can be surpassed by only (1/2 + ϵ)log m comparisons, with ϵ a small positive constant. The even weaker assumption that no improvement in the HLA exists, but that an isolated value t o exists for which the FJA can be surpassed by only (1 + ϵ)log t o comparisons yields the same result. Only for a set of “refractory” integers of size about t 1/2 in the neighborhood of each u k does the FJA fail to be beaten. All these results depend on a new technique for obtaining optimum sort-merge sequences for best-possible sorting given a merging method. The technique turns out to be amenable to precise asymptotic analysis. When the technique is applied using the most powerful known merging algorithm [Christen's], the density mentioned above is still 1, but islands of refractory points still remain, this time forming sets provably of size Θ(log 2 t ) in the neighborhood of each u k . It is shown that if “information theoretic” merging were achievable, the FJA could be beaten for all t > u 10 = 1365. From these results and a few others, we adduce evidence in support of our main conjecture: that even optimum combinations of optimum merging and Ford-Johnson sorting will not beat the FJA when t = u k , but will instead produce refractory regions of size Θ(log 2 t ) in the neighborhood of each λ . Glenn K. Manacher, Tien D. Bui, Mai Thanh |
J. ACM | 3 |