Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Mai Thanh

dblp:16/2680 · DBLP profile ↗
← Back
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

TopicWeightPapersLastEvidence papers
Algorithms and data structures › sequence algorithms › sorting
comparison sorting
0.011989
Optimum combinations of sorting and merging · J. ACM 1989
Computational complexity
lower bounds
0.011989
Optimum combinations of sorting and merging · J. ACM 1989
Algorithms and data structures › sorting and merging
merging
0.011989
Optimum combinations of sorting and merging · J. ACM 1989
Algorithms and data structures
sorting and merging
0.011989
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
YearPublicationVenuePosition
1989 Optimum combinations of sorting and merging
abstract
In 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. ACM3