{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:58:14Z","timestamp":1725566294348},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540230250"},{"type":"electronic","value":"9783540301400"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30140-0_23","type":"book-chapter","created":{"date-parts":[[2010,9,18]],"date-time":"2010-09-18T21:31:13Z","timestamp":1284845473000},"page":"240-251","source":"Crossref","is-referenced-by-count":1,"title":["The Average Case Analysis of Partition Sorts"],"prefix":"10.1007","author":[{"given":"Richard","family":"Cole","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David C.","family":"Kandathil","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"23_CR1","volume-title":"Programming Pearls","author":"J.L. Bentley","year":"2000","unstructured":"Bentley, J.L.: Programming Pearls, 2nd edn. Addison-Wesley, Reading (2000)","edition":"2"},{"issue":"11","key":"23_CR2","doi-asserted-by":"publisher","first-page":"1249","DOI":"10.1002\/spe.4380231105","volume":"23","author":"J.L. Bentley","year":"1993","unstructured":"Bentley, J.L., Douglas McIlroy, M.: Engineering a sort function. Software Practice and Experience\u00a023(11), 1249\u20131265 (1993)","journal-title":"Software Practice and Experience"},{"issue":"3","key":"23_CR3","first-page":"271","volume":"3","author":"J.-C. Chen","year":"1996","unstructured":"Chen, J.-C.: Proportion split sort. Nordic Journal of Computing\u00a03(3), 271\u2013279 (Fall 1996)","journal-title":"Nordic Journal of Computing"},{"issue":"1","key":"23_CR4","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/S0097539798342903","volume":"31","author":"J.-C. Chen","year":"2002","unstructured":"Chen, J.-C.: Proportion extend sort. SIAM Journal on Computing\u00a031(1), 323\u2013330 (2002)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"23_CR5","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/BF01990520","volume":"33","author":"R.D. Dutton","year":"1993","unstructured":"Dutton, R.D.: Weak-heapsort. BIT\u00a033(3), 372\u2013381 (1993)","journal-title":"BIT"},{"key":"23_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/3-540-46541-3_21","volume-title":"STACS 2000","author":"S. Edelkamp","year":"2000","unstructured":"Edelkamp, S., Wegener, I.: On the performance of weak-heapsort. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol.\u00a01770, pp. 254\u2013266. Springer, Heidelberg (2000)"},{"doi-asserted-by":"crossref","unstructured":"Franceschini, G., Geffert, V.: An in-place sorting with O(n log n) comparisons and O(n) moves. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Cambridge, Massachusetts, October 11-14, pp. 242\u2013250 (2003)","key":"23_CR7","DOI":"10.1109\/SFCS.2003.1238198"},{"issue":"5","key":"23_CR8","doi-asserted-by":"publisher","first-page":"387","DOI":"10.2307\/2308750","volume":"66","author":"L.R. Ford Jr.","year":"1959","unstructured":"Ford Jr., L.R., Johnson, S.M.: A tournament problem. The American Mathematical Monthly\u00a066(5), 387\u2013389 (1959)","journal-title":"The American Mathematical Monthly"},{"issue":"12","key":"23_CR9","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/355588.365103","volume":"7","author":"R.W. Floyd","year":"1964","unstructured":"Floyd, R.W.: ACM Algorithm 245: Treesort 3. Communications of the ACM\u00a07(12), 701 (1964)","journal-title":"Communications of the ACM"},{"issue":"7","key":"23_CR10","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/366622.366644","volume":"4","author":"C.A.R. Hoare","year":"1961","unstructured":"Hoare, C.A.R.: ACM Algorithm 63: Partition, ACM Algorithm 64: Quicksort. Communications of the ACM\u00a04(7), 321\u2013322 (1961)","journal-title":"Communications of the ACM"},{"issue":"1","key":"23_CR11","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1093\/comjnl\/5.1.10","volume":"5","author":"C.A.R. Hoare","year":"1962","unstructured":"Hoare, C.A.R.: Quicksort. The Computer Journal\u00a05(1), 10\u201316 (1962)","journal-title":"The Computer Journal"},{"key":"23_CR12","series-title":"Sorting and Searching","volume-title":"The Art of Computer Programming","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: The Art of Computer Programming. Sorting and Searching, vol.\u00a03. Addison-Wesley, Reading (1973)"},{"issue":"1","key":"23_CR13","first-page":"27","volume":"3","author":"J. Katajainen","year":"1996","unstructured":"Katajainen, J., Pasanen, T., Teuhola, J.: Practical in-place mergesort. Nordic Journal of Computing\u00a03(1), 27\u201340 (Spring 1996)","journal-title":"Nordic Journal of Computing"},{"unstructured":"LaMarca, A., Ladner, R.E.: The influence of caches on the performance of sorting. In: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, January 5-7, pp. 370\u2013379 (1997)","key":"23_CR14"},{"issue":"8","key":"23_CR15","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1002\/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#","volume":"27","author":"D.R. Musser","year":"1997","unstructured":"Musser, D.R.: Introspective sorting and selection algorithms. Software Practice and Experience\u00a027(8), 983\u2013993 (1997)","journal-title":"Software Practice and Experience"},{"issue":"2","key":"23_CR16","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1137\/0214030","volume":"14","author":"R. Reischuk","year":"1985","unstructured":"Reischuk, R.: Probabilistic parallel algorithms for sorting and selection. SIAM Journal on Computing\u00a014(2), 396\u2013409 (1985)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1007\/3-540-56279-6_101","volume-title":"Algorithms and Computation","author":"K. Reinhardt","year":"1992","unstructured":"Reinhardt, K.: Sorting in-place with a worst case complexity of n log n \u2013 1.3n + o(log n) comparisons and \u03b5n log n + o(1) transports. In: Ibaraki, T., Iwama, K., Yamashita, M., Inagaki, Y., Nishizeki, T. (eds.) ISAAC 1992. LNCS, vol.\u00a0650, pp. 489\u2013498. Springer, Heidelberg (1992)"},{"issue":"10","key":"23_CR18","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1145\/359619.359631","volume":"21","author":"R. Sedgewick","year":"1978","unstructured":"Sedgewick, R.: Implementing quicksort programs. Communications of the ACM\u00a021(10), 847\u2013857 (1978)","journal-title":"Communications of the ACM"},{"issue":"3","key":"23_CR19","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1145\/362875.362901","volume":"12","author":"R.C. Singleton","year":"1969","unstructured":"Singleton, R.C.: An efficient algorithm for sorting with minimal storage. Communications of the ACM\u00a012(3), 185\u2013187 (1969)","journal-title":"Communications of the ACM"},{"issue":"1","key":"23_CR20","doi-asserted-by":"publisher","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). Theoretical Computer Science\u00a0118(1), 81\u201398 (1993)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"23_CR21","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J.W.J. Williams","year":"1964","unstructured":"Williams, J.W.J.: ACM Algorithm 232: Heapsort. Communications of the ACM\u00a07(6), 347\u2013348 (1964)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30140-0_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,10]],"date-time":"2021-11-10T00:24:37Z","timestamp":1636503877000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30140-0_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230250","9783540301400"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30140-0_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}