How good is the information theory bound in sorting?
From MaRDI portal
Publication:1226391
DOI10.1016/0304-3975(76)90078-5zbMath0327.68056OpenAlexW2091505308MaRDI QIDQ1226391
Publication date: 1976
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(76)90078-5
Analysis of algorithms and problem complexity (68Q25) Information theory (general) (94A15) Algorithms in computer science (68W99)
Related Items
Sublinear merging and natural mergesort, A family of partially ordered sets with small balance constant, Selection and sorting in totally monotone arrays, A framework for adaptive sorting, Better lower bounds on detecting affine and spherical degeneracies, Linear extensions of infinite posets, Balancing pairs and the cross product conjecture, Topologically sweeping an arrangement, Four Soviets walk the dog: improved bounds for computing the Fréchet distance, Subquadratic algorithms for algebraic 3SUM, The cross-product conjecture for width two posets, Computing and ranking measures of presortedness, Unnamed Item, Sorting probability for large Young diagrams, Sorting under partial information (without the ellipsoid algorithm)., Balancing extensions via Brunn-Minkowski, On the conductance of order Markov chains, A pseudo-algorithmic separation of lines from pseudo-lines, Necklaces, convolutions, and \(X+Y\), An algorithm for computing exact least-trimmed squares estimate of simple linear regression with constraints, Sorting the sums \((x_ i+y_ j)\) in \(O(n^ 2)\) comparisons, The complexity of lexicographic sorting and searching, Balance theorems for height-2 posets, Adaptive sorting: an information theoretic perspective, Tight bounds for online stable sorting, Balancing poset extensions, Linear extensions and comparable pairs in partial orders, On the \(1/3-2/3\) conjecture, Connected Rectilinear Graphs on Point Sets, Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets, A note on average-case sorting, Sorting and Selection with Random Costs, A framework for adaptive sorting, Lower bounds for sorting of sums, A strange pigeon-hole principle, Preprocessing Ambiguous Imprecise Points, Semiorders and the 1/3-2/3 conjecture, Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy, On Generalized Comparison-Based Sorting Problems, Balanced pairs in partial orders, Dominance Product and High-Dimensional Closest Pair under L_infty, Space-time trade-offs for some ranking and searching queries, Every poset has a central element
Cites Work
