{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T19:11:45Z","timestamp":1792782705346,"version":"4.5.0"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T00:00:00Z","timestamp":1777939200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T00:00:00Z","timestamp":1777939200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Ministry of Education and Science of Bulgaria","id":[{"id":"https:\/\/ror.org\/053pcb396","id-type":"ROR","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["949272"],"award-info":[{"award-number":["949272"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008398","name":"Villum Fonden","doi-asserted-by":"publisher","award":["54451"],"award-info":[{"award-number":["54451"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002661","name":"Fonds De La Recherche Scientifique - FNRS","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004318","name":"Microsoft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004318","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We consider the problem of sorting\n                    <jats:italic>n<\/jats:italic>\n                    items, given the outcomes of\n                    <jats:italic>m<\/jats:italic>\n                    pre-existing comparisons. We present a simple and natural deterministic algorithm that runs in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\textrm{O}(m+\\log T)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mtext>O<\/mml:mtext>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>m<\/mml:mi>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mo>log<\/mml:mo>\n                            <mml:mi>T<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    time and does\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\textrm{O}(\\log T)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mtext>O<\/mml:mtext>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mo>log<\/mml:mo>\n                            <mml:mi>T<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    comparisons, where\n                    <jats:italic>T<\/jats:italic>\n                    is the number of total orders consistent with the pre-existing comparisons. Our running time and comparison bounds are best possible up to constant factors, thus resolving a problem that has been studied intensely since 1976 (Fredman, Theoretical Computer Science). The best previous algorithm with a bound of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\textrm{O}(\\log T)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mtext>O<\/mml:mtext>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mo>log<\/mml:mo>\n                            <mml:mi>T<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    on the number of comparisons has a time bound of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\textrm{O}(n^{2.5})$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mtext>O<\/mml:mtext>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>n<\/mml:mi>\n                              <mml:mrow>\n                                <mml:mn>2.5<\/mml:mn>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    and is more complicated. Our algorithm combines three classic algorithms: topological sort, heapsort with the right kind of heap, and efficient search in a sorted list. It outputs the items in sorted order one by one. It can be modified to stop early, thereby solving the important and more general top-\n                    <jats:italic>k<\/jats:italic>\n                    sorting problem: Given\n                    <jats:italic>k<\/jats:italic>\n                    and the outcomes of some pre-existing comparisons, output the smallest\n                    <jats:italic>k<\/jats:italic>\n                    items in sorted order. The modified algorithm solves the top-\n                    <jats:italic>k<\/jats:italic>\n                    sorting problem in minimum time and comparisons, to within constant factors.\n                  <\/jats:p>","DOI":"10.1007\/s00453-026-01387-3","type":"journal-article","created":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T10:53:43Z","timestamp":1777978423000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast and Simple Sorting Using Partial Information"],"prefix":"10.1007","volume":"88","author":[{"given":"Bernhard","family":"Haeupler","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Hlad\u00edk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Iacono","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"V\u00e1clav","family":"Rozho\u0148","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jakub","family":"T\u011btek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,5,5]]},"reference":[{"key":"1387_CR1","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Hlad\u00edk, R., Iacono, J., Rozhon, V., Tarjan, R.E., Tetek, J.: Fast and simple sorting using partial information. In: Azar, Y., Panigrahi, D. (eds.) Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12\u201315, 2025, pp. 3953\u20133973. SIAM (2025)","DOI":"10.1137\/1.9781611978322.134"},{"key":"1387_CR2","doi-asserted-by":"crossref","unstructured":"Kahn, J., Kim, J.H.: Entropy and sorting. In: Proceedings of the Twenty-fourth Annual ACM Symposium on Theory of Computing, pp. 178\u2013187 (1992)","DOI":"10.1145\/129712.129731"},{"issue":"4","key":"1387_CR3","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0304-3975(76)90078-5","volume":"1","author":"ML Fredman","year":"1976","unstructured":"Fredman, M.L.: How good is the information theory bound in sorting? Theoret. Comput. Sci. 1(4), 355\u2013361 (1976)","journal-title":"Theoret. Comput. Sci."},{"key":"1387_CR4","doi-asserted-by":"crossref","unstructured":"Hoog, I., Rutschmann, D.: Tight bounds for sorting under partial information. In: 65th IEEE Annual Symposium on Foundations of Computer Science, pp. 2243\u20132252 (2024)","DOI":"10.1109\/FOCS61266.2024.00131"},{"key":"1387_CR5","doi-asserted-by":"crossref","unstructured":"Williams, V.V., Xu, Y., Xu, Z., Zhou, R.: New bounds for matrix multiplication: from alpha to omega. In: 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 3792\u20133835 (2024)","DOI":"10.1137\/1.9781611977912.134"},{"key":"1387_CR6","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Hlad\u00edk, R., Rozhon, V., Tarjan, R.E., Tetek, J.: Universal optimality of dijkstra via beyond-worst-case heaps. In: 65th IEEE Annual Symposium on Foundations of Computer Science, pp. 2099\u20132130. IEEE (2024)","DOI":"10.1109\/FOCS61266.2024.00125"},{"key":"1387_CR7","doi-asserted-by":"crossref","unstructured":"Hoog, I., Rotenberg, E., Rutschmann, D.: Simpler optimal sorting from a directed acyclic graph. In: 2025 Symposium on Simplicity in Algorithms, pp. 350\u2013355 (2025)","DOI":"10.1137\/1.9781611978315.26"},{"key":"1387_CR8","unstructured":"Haeupler, B., Hlad\u00edk, R., Iacono, J., Rozhon, V., Tarjan, R., T\u011btek, J.: Fast and Simple Sorting Using Partial Information (2024). https:\/\/arxiv.org\/abs\/2404.04552"},{"key":"1387_CR9","doi-asserted-by":"publisher","unstructured":"Yao, A.C.: Probabilistic computations: Toward a unified measure of complexity (extended abstract). In: 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977, pp. 222\u2013227. IEEE Computer Society (1977). https:\/\/doi.org\/10.1109\/SFCS.1977.24","DOI":"10.1109\/SFCS.1977.24"},{"issue":"3","key":"1387_CR10","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"issue":"3","key":"1387_CR11","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32(3), 652\u2013686 (1985)","journal-title":"J. ACM"},{"key":"1387_CR12","doi-asserted-by":"crossref","unstructured":"Iacono, J.: Improved upper bounds for pairing heaps. In: Scandinavian Workshop on Algorithm Theory, pp. 32\u201345. Springer (2000)","DOI":"10.1007\/3-540-44985-X_5"},{"issue":"1\u20134","key":"1387_CR13","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01840439","volume":"1","author":"ML Fredman","year":"1986","unstructured":"Fredman, M.L., Sedgewick, R., Sleator, D.D., Tarjan, R.E.: The pairing heap: a new form of self-adjusting heap. Algorithmica 1(1\u20134), 111\u2013129 (1986)","journal-title":"Algorithmica"},{"issue":"5","key":"1387_CR14","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1007\/BF01111312","volume":"5","author":"SS Kislitsin","year":"1968","unstructured":"Kislitsin, S.S.: A finite partially ordered set and its corresponding set of permutations. Math. Notes 5(5), 798\u2013801 (1968)","journal-title":"Math. Notes"},{"issue":"4","key":"1387_CR15","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1137\/0213049","volume":"13","author":"N Linial","year":"1984","unstructured":"Linial, N.: The information-theoretic bound is good for merging. SIAM J. Comput. 13(4), 795\u2013801 (1984)","journal-title":"SIAM J. Comput."},{"key":"1387_CR16","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF00565647","volume":"1","author":"J Kahn","year":"1984","unstructured":"Kahn, J., Saks, M.: Balancing poset extensions. Order 1, 113\u2013126 (1984)","journal-title":"Order"},{"issue":"4","key":"1387_CR17","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/BF01275670","volume":"11","author":"J Kahn","year":"1991","unstructured":"Kahn, J., Linial, N.: Balancing extensions via Brunn-Minkowski. Combinatorica 11(4), 363\u2013368 (1991)","journal-title":"Combinatorica"},{"key":"1387_CR18","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF01110378","volume":"12","author":"GR Brightwell","year":"1995","unstructured":"Brightwell, G.R., Felsner, S., Trotter, W.T.: Balancing pairs and the cross product conjecture. Order 12, 327\u2013349 (1995)","journal-title":"Order"},{"issue":"1\u20133","key":"1387_CR19","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/S0012-365X(98)00311-2","volume":"201","author":"G Brightwell","year":"1999","unstructured":"Brightwell, G.: Balanced pairs in partial orders. Discret. Math. 201(1\u20133), 25\u201352 (1999)","journal-title":"Discret. Math."},{"key":"1387_CR20","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1137\/0201004","volume":"1","author":"FK Hwang","year":"1972","unstructured":"Hwang, F.K., Lin, S.: A simple algorithm for merging two disjoint linearly ordered sets. SIAM J. Comput. 1, 31\u201339 (1972)","journal-title":"SIAM J. Comput."},{"key":"1387_CR21","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1145\/322123.322127","volume":"26","author":"MR Brown","year":"1979","unstructured":"Brown, M.R., Tarjan, R.E.: A fast merging algorithm. J. Assoc. Comput. Mach. 26, 211\u2013226 (1979)","journal-title":"J. Assoc. Comput. Mach."},{"key":"1387_CR22","doi-asserted-by":"crossref","unstructured":"Cardinal, J., Fiorini, S., Joret, G., Jungers, R.M., Munro, J.I.: Sorting under partial information (without the ellipsoid algorithm). In: Proceedings of the Forty-second ACM Symposium on Theory of Computing, pp. 359\u2013368 (2010)","DOI":"10.1145\/1806689.1806740"},{"key":"1387_CR23","unstructured":"Christiano, P.F., Leike, J., Brown, T., Martic, M., Legg, S., Amodei, D.: Deep reinforcement learning from human preferences. Adv. Neural Inf. Process. Syst. 30 (2017)"},{"key":"1387_CR24","doi-asserted-by":"crossref","unstructured":"Dushkin, E., Milo, T.: Top-k sorting under partial order information. In: Proceedings of the 2018 International Conference on Management of Data, pp. 1007\u20131019 (2018)","DOI":"10.1145\/3183713.3199672"},{"issue":"4","key":"1387_CR25","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V.R., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci. 7(4), 448\u2013461 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"1387_CR26","doi-asserted-by":"crossref","unstructured":"Cardinal, J., Fiorini, S.: On generalized comparison-based sorting problems. In: Space-Efficient Data Structures, Streams, and Algorithms: Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, pp. 164\u2013175. Springer (2013)","DOI":"10.1007\/978-3-642-40273-9_12"},{"issue":"06","key":"1387_CR27","doi-asserted-by":"publisher","first-page":"1455","DOI":"10.1142\/S0129054106004510","volume":"17","author":"A Elmasry","year":"2006","unstructured":"Elmasry, A.: A priority queue with the working-set property. Int. J. Found. Comput. Sci. 17(06), 1455\u20131465 (2006)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"1387_CR28","doi-asserted-by":"crossref","unstructured":"Kozma, L., Saranurak, T.: Smooth heaps and a dual view of self-adjusting data structures. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 801\u2013814 (2018)","DOI":"10.1145\/3188745.3188864"},{"key":"1387_CR29","doi-asserted-by":"publisher","unstructured":"Munro, J.I., Peng, R., Wild, S., Zhang, L.: Dynamic optimality refuted - for tournament heaps (2019). https:\/\/doi.org\/10.48550\/arXiv.1908.00563","DOI":"10.48550\/arXiv.1908.00563"},{"issue":"4","key":"1387_CR30","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s00236-013-0180-8","volume":"50","author":"A Elmasry","year":"2013","unstructured":"Elmasry, A., Farzan, A., Iacono, J.: On the hierarchy of distribution-sensitive properties for data structures. Acta Informatica 50(4), 289\u2013295 (2013)","journal-title":"Acta Informatica"},{"key":"1387_CR31","doi-asserted-by":"crossref","unstructured":"Bose, P., Howat, J., Morin, P.: A history of distribution-sensitive data structures. Space-Efficient Data Structures, Streams, and Algorithms: Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, pp. 133\u2013149 (2013)","DOI":"10.1007\/978-3-642-40273-9_10"},{"issue":"3","key":"1387_CR32","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1006\/jagm.1993.1021","volume":"14","author":"C Levcopoulos","year":"1993","unstructured":"Levcopoulos, C., Petersson, O.: Adaptive heapsort. J. Algorithms 14(3), 395\u2013413 (1993)","journal-title":"J. Algorithms"},{"key":"1387_CR33","first-page":"229","volume":"38\u201339","author":"A Sch\u00f6nhage","year":"1976","unstructured":"Sch\u00f6nhage, A.: The production of partial orders. Ast\u00e9risque 38\u201339, 229\u2013246 (1976)","journal-title":"Ast\u00e9risque"},{"issue":"4","key":"1387_CR34","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1137\/0218047","volume":"18","author":"AC Yao","year":"1989","unstructured":"Yao, A.C.: On the complexity of partial order productions. SIAM J. Comput. 18(4), 679\u2013689 (1989)","journal-title":"SIAM J. Comput."},{"key":"1387_CR35","doi-asserted-by":"crossref","unstructured":"Cardinal, J., Fiorini, S., Joret, G., Jungers, R.M., Munro, J.I.: An efficient algorithm for partial order production. In: Mitzenmacher, M. (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31\u2013June 2, 2009, pp. 93\u2013100. ACM (2009)","DOI":"10.1145\/1536414.1536430"},{"key":"1387_CR36","doi-asserted-by":"crossref","unstructured":"Brightwell, G., Winkler, P.: Counting linear extensions is #p-complete. In: Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, pp. 175\u2013181 (1991)","DOI":"10.1145\/103418.103441"},{"issue":"1","key":"1387_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/102782.102783","volume":"38","author":"M Dyer","year":"1991","unstructured":"Dyer, M., Frieze, A., Kannan, R.: A random polynomial-time algorithm for approximating the volume of convex bodies. J. ACM 38(1), 1\u201317 (1991)","journal-title":"J. ACM"},{"key":"1387_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jda.2018.04.001","volume":"51","author":"J Banks","year":"2018","unstructured":"Banks, J., Garrabrant, S.M., Huber, M.L., Perizzolo, A.: Using TPA to count linear extensions. J. Discrete Algorithms 51, 1\u201311 (2018)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"1387_CR39","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1214\/aop\/1176990349","volume":"19","author":"P Matthews","year":"1991","unstructured":"Matthews, P.: Generating a random linear extension of a partial order. Ann. Probab. 19(3), 1367\u20131392 (1991)","journal-title":"Ann. Probab."},{"key":"1387_CR40","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF00385809","volume":"8","author":"A Karzanov","year":"1991","unstructured":"Karzanov, A., Khachiyan, L.: On the conductance of order Markov chains. Order 8, 7\u201315 (1991)","journal-title":"Order"},{"issue":"1\u20133","key":"1387_CR41","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0012-365X(98)00333-1","volume":"201","author":"R Bubley","year":"1999","unstructured":"Bubley, R., Dyer, M.: Faster random generation of linear extensions. Discret. Math. 201(1\u20133), 81\u201388 (1999)","journal-title":"Discret. Math."},{"issue":"4","key":"1387_CR42","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1016\/j.disc.2006.01.003","volume":"306","author":"M Huber","year":"2006","unstructured":"Huber, M.: Fast perfect sampling from linear extensions. Discret. Math. 306(4), 420\u2013428 (2006)","journal-title":"Discret. Math."},{"key":"1387_CR43","volume-title":"The Art of Computer Programming: Fundamental Algorithms","author":"DE Knuth","year":"1997","unstructured":"Knuth, D.E.: The Art of Computer Programming: Fundamental Algorithms, vol. 1. Addison-Wesley Professional (1997)"},{"issue":"6","key":"1387_CR44","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1145\/512274.3734138","volume":"7","author":"J Williams","year":"1964","unstructured":"Williams, J.: Heapsort. Commun. ACM 7(6), 347\u2013348 (1964)","journal-title":"Commun. ACM"},{"issue":"12","key":"1387_CR45","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/355588.365103","volume":"7","author":"RW Floyd","year":"1964","unstructured":"Floyd, R.W.: Algorithm 245: treesort. Commun. ACM 7(12), 701 (1964)","journal-title":"Commun. ACM"},{"issue":"11","key":"1387_CR46","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/368996.369025","volume":"5","author":"AB Kahn","year":"1962","unstructured":"Kahn, A.B.: Topological sorting of large networks. Commun. ACM 5(11), 558\u2013562 (1962)","journal-title":"Commun. ACM"},{"issue":"3","key":"1387_CR47","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","volume":"27","author":"CE Shannon","year":"1948","unstructured":"Shannon, C.E.: A mathematical theory of communication. Bell Syst. Tech. J. 27(3), 379\u2013423 (1948)","journal-title":"Bell Syst. Tech. J."},{"key":"1387_CR48","doi-asserted-by":"crossref","unstructured":"Sinnamon, C., Tarjan, R.E.: Efficiency of self-adjusting heaps. ACM Trans. Algorithms (2025)","DOI":"10.1145\/3708989"},{"key":"1387_CR49","unstructured":"Sinnamon, C., Tarjan, R.E.: A simpler proof that pairing heaps take O(1) amortized time per insertion (2022). CoRR: arXiv:abs\/2208.11791"},{"issue":"2","key":"1387_CR50","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"RE Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Amortized computational complexity. SIAM J. Algebraic Discret. Methods 6(2), 306\u2013318 (1985)","journal-title":"SIAM J. Algebraic Discret. Methods"},{"key":"1387_CR51","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S Huddleston","year":"1982","unstructured":"Huddleston, S., Mehlhorn, K.: A new data structure for representing sorted lists. Acta Informatica 17, 157\u2013184 (1982). https:\/\/doi.org\/10.1007\/BF00288968","journal-title":"Acta Informatica"},{"key":"1387_CR52","doi-asserted-by":"publisher","unstructured":"Tsakalidis, A.K.: Maintaining order in a generalized linked list. In: Cremers, A.B., Kriegel, H. (eds.) Theoretical Computer Science, 6th GI-Conference, Dortmund, Germany, January 5\u20137, 1983, Proceedings. Lecture Notes in Computer Science, vol. 145, pp. 343\u2013352. Springer (1983). https:\/\/doi.org\/10.1007\/BFB0009658","DOI":"10.1007\/BFB0009658"},{"key":"1387_CR53","doi-asserted-by":"publisher","unstructured":"Dietz, P.F., Sleator, D.D.: Two algorithms for maintaining order in a list. In: Aho, A.V. (ed.) Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pp. 365\u2013372. ACM (1987). https:\/\/doi.org\/10.1145\/28395.28434","DOI":"10.1145\/28395.28434"},{"key":"1387_CR54","doi-asserted-by":"publisher","unstructured":"Bender, M.A., Cole, R., Demaine, E.D., Farach-Colton, M., Zito, J.: Two simplified algorithms for maintaining order in a list. In: M\u00f6hring, R.H., Raman, R. (eds.) Algorithms - ESA 2002, 10th Annual European Symposium, Rome, Italy, September 17-21, 2002, Proceedings. Lecture Notes in Computer Science, vol. 2461, pp. 152\u2013164. Springer (2002). https:\/\/doi.org\/10.1007\/3-540-45749-6_17","DOI":"10.1007\/3-540-45749-6_17"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01387-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01387-3","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01387-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,22]],"date-time":"2026-10-22T06:14:31Z","timestamp":1792649671000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01387-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,5]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["1387"],"URL":"https:\/\/doi.org\/10.1007\/s00453-026-01387-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,5]]},"assertion":[{"value":"20 February 2026","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 March 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 May 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 October 2026","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"\"This article was originally published under the subscription model but it is now published under an Open Access license.\"","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 2026","order":8,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":9,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This article was originally published under the subscription model but it is now published under an Open Access license.","order":10,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no conflict of interest.","order":1,"name":"Ethics","label":"Conflict of interest","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"41"}}