{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:53Z","timestamp":1750308773216,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002808","name":"Carlsbergfondet","doi-asserted-by":"publisher","award":["ANS-0257\/20"],"award-info":[{"award-number":["ANS-0257\/20"]}],"id":[{"id":"10.13039\/501100002808","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>\n            Quicksort was first introduced in 1961 by Hoare. Many variants have been developed, the best of which are among the fastest generic-sorting algorithms available, as testified by the choice of Quicksort as the default sorting algorithm in most programming libraries. Some sorting algorithms are adaptive, i.e., they have a complexity analysis that is better for inputs, which are nearly sorted, according to some specified measure of presortedness. Quicksort is not among these, as it uses \u03a9(\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) comparisons even for sorted inputs. However, in this paper, we demonstrate empirically that the actual running time of Quicksort\n            <jats:italic>is<\/jats:italic>\n            adaptive with respect to the presortedness measure Inv. Differences close to a factor of two are observed between instances with low and high Inv value. We then show that for the randomized version of Quicksort, the number of element\n            <jats:italic>swaps<\/jats:italic>\n            performed is\n            <jats:italic>provably<\/jats:italic>\n            adaptive with respect to the measure Inv. More precisely, we prove that randomized Quicksort performs expected\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            (1 + log(1 + Inv\/\n            <jats:italic>n<\/jats:italic>\n            ))) element swaps, where Inv denotes the number of inversions in the input sequence. This result provides a theoretical explanation for the observed behavior and gives new insights on the behavior of Quicksort. We also give some empirical results on the adaptive behavior of Heapsort and Mergesort.\n          <\/jats:p>","DOI":"10.1145\/1227161.1402294","type":"journal-article","created":{"date-parts":[[2008,10,8]],"date-time":"2008-10-08T13:57:58Z","timestamp":1223474278000},"page":"1-20","source":"Crossref","is-referenced-by-count":6,"title":["On the adaptiveness of Quicksort"],"prefix":"10.1145","volume":"12","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[{"name":"MADALGO, University of Aarhus, \u00c5rhus N, Denmark"}]},{"given":"Rolf","family":"Fagerberg","sequence":"additional","affiliation":[{"name":"University of Southern Denmark, Odense M, Denmark"}]},{"given":"Gabriel","family":"Moruz","sequence":"additional","affiliation":[{"name":"J. W. Goethe University, Frankfurt\/Main, Germany"}]}],"member":"320","published-online":{"date-parts":[[2008,8,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","unstructured":"Bentley J. L. and McIlroy M. D. 1993. Engineering a sort function. Software\u2014Practice and Experience 23 11 (Nov.) 1249--1265. 10.1002\/spe.4380231105","DOI":"10.1002\/spe.4380231105"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11534273_34"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_47"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684272"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/1-4020-8141-3_25"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/646517.694058"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_52"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/146370.146381"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/355588.365103"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946313"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366642"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366644"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/5.1.1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/280635"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382108"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Mehlhorn K. 1984. Sorting and Searching. Springer Verlag Berlin.","DOI":"10.1007\/978-3-642-69672-5_2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/646335.688104"},{"key":"e_1_2_1_18_1","volume-title":"12th Annual European Symposium on Algorithms, ESA","volume":"3221","author":"Pagh A.","year":"2004","unstructured":"Pagh, A., Pagh, R., and Thorup, M. 2004. On adaptive integer sorting. In 12th Annual European Symposium on Algorithms, ESA 2004. Lecture Notes in Computer Science, vol. 3221. Springer Verlag, Berlin. 556--567."},{"key":"e_1_2_1_19_1","unstructured":"papi 2004. PAPI (Performance Application Programming Interface). Software library found at http:\/\/icl.cs.utk.edu\/papi\/."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)E0160-Z"},{"key":"e_1_2_1_21_1","volume-title":"12th Annual European Symposium on Algorithms, ESA","volume":"3221","author":"Sanders P.","year":"2004","unstructured":"Sanders, P. and Winkel, S. 2004. Super scalar sample sort. In 12th Annual European Symposium on Algorithms, ESA 2004. Lecture Notes in Computer Science, vol. 3221. Springer Verlag, Berlin. 784--796."},{"volume-title":"thesis","author":"Sedgewick R.","key":"e_1_2_1_22_1","unstructured":"Sedgewick, R. 1975. Quicksort. Ph.D. thesis, Stanford University, Stanford, CA. Stanford Computer Science Report STAN-CS-75-492."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289467"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359631"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/647906.739656"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/368370.368387"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/512274.512284"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1402294","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1227161.1402294","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:37Z","timestamp":1750278157000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1402294"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":27,"alternative-id":["10.1145\/1227161.1402294"],"URL":"https:\/\/doi.org\/10.1145\/1227161.1402294","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}