{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:06:49Z","timestamp":1761808009081},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,9,15]],"date-time":"2015-09-15T00:00:00Z","timestamp":1442275200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,8]]},"DOI":"10.1007\/s00224-015-9656-y","type":"journal-article","created":{"date-parts":[[2015,9,15]],"date-time":"2015-09-15T05:45:47Z","timestamp":1442295947000},"page":"209-230","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["QuickHeapsort: Modifications and Improved Analysis"],"prefix":"10.1007","volume":"59","author":[{"given":"Volker","family":"Diekert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Armin","family":"Wei\u00df","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,9,15]]},"reference":[{"issue":"4","key":"9656_CR1","doi-asserted-by":"crossref","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., 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."},{"issue":"1","key":"9656_CR2","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0304-3975(01)00288-2","volume":"285","author":"D Cantone","year":"2002","unstructured":"Cantone, D., Cincotti, G.: QuickHeapsort, an efficient mix of classical sorting algorithms. Theor. Comput. Sci. 285(1), 25\u201342 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9656_CR3","doi-asserted-by":"crossref","unstructured":"Carlsson, S., Chen, J., Mattsson, C.: Heaps with Bits. In: D.-Z. Du, X.-S. Zhang (eds.) ISAAC, vol. 834 of LNCS, pp. 288\u2013296. Springer (1994)","DOI":"10.1007\/3-540-58325-4_192"},{"key":"9656_CR4","doi-asserted-by":"crossref","unstructured":"Chen, J.: A Framework for Constructing Heap-like structures in-place. In: K.-W. Ng, et al. (eds.) ISAAC, vol. 762 of LNCS, pp. 118\u2013127. Springer (1993)","DOI":"10.1007\/3-540-57568-5_241"},{"key":"9656_CR5","doi-asserted-by":"crossref","unstructured":"Chen, J., Edelkamp, S., Elmasry, A., Katajainen, J.: In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses. In: B. Rovan, V. Sassone, P. Widmayer (eds.) MFCS, vol. 7464 of LNCS, pp. 259\u2013270. Springer (2012)","DOI":"10.1007\/978-3-642-32589-2_25"},{"key":"9656_CR6","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. The MIT Press, 3rd edn. (2009)"},{"issue":"3","key":"9656_CR7","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1007\/BF01990520","volume":"33","author":"RD Dutton","year":"1993","unstructured":"Dutton, R.D.: Weak-heap sort. BIT 33(3), 372\u2013381 (1993)","journal-title":"BIT"},{"key":"9656_CR8","doi-asserted-by":"crossref","unstructured":"Edelkamp, S., Stiegeler, P.: Implementing HEAPSORT with n lg n \u2212 0.9 n $n \\lg n - 0.9n$ and QUICKSORT with n lg n + 0.2 n $n \\lg n + 0.2n$ comparisons. ACM J. of Exp. Alg., 7:5 (2002)","DOI":"10.1145\/944618.944623"},{"issue":"12","key":"9656_CR9","doi-asserted-by":"crossref","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":"4","key":"9656_CR10","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1137\/0215068","volume":"15","author":"GH Gonnet","year":"1986","unstructured":"Gonnet, G.H., Munro, J.I.: Heaps on Heaps. SIAM J. Comput. 15(4), 964\u2013971 (1986)","journal-title":"SIAM J. Comput."},{"key":"9656_CR11","unstructured":"Katajainen, J.: The ultimate heapsort. In: X. Lin (ed.) CATS, vol. 20 of Australian Computer Science Communications, pp. 87\u201396. Springer-Verlag (1998)"},{"key":"9656_CR12","unstructured":"Knuth, D.E.: The art of computer programming. vol. 3 Addison-Wesley (1998)"},{"issue":"3","key":"9656_CR13","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1137\/S0097539700382108","volume":"31","author":"C Mart\u00ednez","year":"2001","unstructured":"Mart\u00ednez, C., Roura, S.: Optimal sampling strategies in Quicksort and Quickselect. SIAM J. Comput. 31(3), 683\u2013705 (2001)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9656_CR14","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1016\/0196-6774(89)90033-3","volume":"10","author":"C McDiarmid","year":"1989","unstructured":"McDiarmid, C., Reed, B.A.: Building Heaps Fast. J. Alg. 10(3), 352\u2013365 (1989)","journal-title":"J. Alg."},{"key":"9656_CR15","doi-asserted-by":"crossref","unstructured":"Reinhardt, K.: Sorting in-place with a worst case complexity of n log n \u2212 1.3 n + O ( log n ) $ n \\log n -1.3 n + O(\\log n)$ comparisons and \ud835\udf16n log n + O ( 1 ) $\\epsilon n \\log n + O(1)$ transports. In: T. Ibaraki, et al. (eds.) ISAAC, vol. 650 of LNCS, pp. 489\u2013498. Springer (1992)","DOI":"10.1007\/3-540-56279-6_101"},{"key":"9656_CR16","doi-asserted-by":"crossref","first-page":"898","DOI":"10.1007\/s11390-007-9106-7","volume":"22","author":"X-D Wang","year":"2007","unstructured":"Wang, X.-D., Wu, Y.-J.: An improved HEAPSORT Algorithm with n lg n \u2212 0.788928 n $n\\lg n - 0.788928n$ comparisons in the Worst Case. J. Comput. Sci. Techn. 22, 898\u2013903 (2007)","journal-title":"J. Comput. Sci. Techn."},{"key":"9656_CR17","doi-asserted-by":"crossref","unstructured":"Wegener, I.: The worst case complexity of McDiarmid and Reed\u2019s variant of Bottom-Up-Heap sort is less than n lg n + 1.1 n $n \\lg n + 1.1n$ . In: C. Choffrut, M. Jantzen (eds.) STACS, vol. 480 of LNCS, pp. 137\u2013147. Springer (1991)","DOI":"10.1007\/BFb0020794"},{"issue":"1","key":"9656_CR18","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0304-3975(93)90364-Y","volume":"118","author":"I Wegener","year":"1993","unstructured":"Wegener, I.: BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT, beating, on an average, QUICKSORT (if n is not very small). Theor. Comp. Sci. 118(1), 81\u201398 (1993)","journal-title":"Theor. Comp. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9656-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-015-9656-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9656-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,30]],"date-time":"2019-08-30T14:59:22Z","timestamp":1567177162000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-015-9656-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,15]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,8]]}},"alternative-id":["9656"],"URL":"https:\/\/doi.org\/10.1007\/s00224-015-9656-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,15]]}}}