{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T02:10:04Z","timestamp":1750299004450,"version":"3.41.0"},"reference-count":5,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,12,27]],"date-time":"2024-12-27T00:00:00Z","timestamp":1735257600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2024,12,27]]},"abstract":"<jats:p>\n            We introduce the algorithm ExpoSort, a groundbreaking method that sorts an array of n numbers in a spectacularly inefficient \u0398(2\n            <jats:sup>n<\/jats:sup>\n            ) time. ExpoSort proudly claims the title of the first reluctant algorithm to decisively surpass the quasi-polynomial running time \u03a9(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>log n\/(2+\u03b5)<\/jats:sup>\n            ) of the notoriously sluggish\n            <jats:sc>SlowSort<\/jats:sc>\n            algorithm by Broder and Stolfi [ACM SIGACT News, 1984]. In the ongoing quest for the slowest possible sort,\n            <jats:sc>ExpoSort<\/jats:sc>\n            redefines what it means to take one's time.\n          <\/jats:p>\n          <jats:p>\n            Remarkably,\n            <jats:sc>ExpoSort<\/jats:sc>\n            achieves this feat with one of the simplest pseudocodes among all known sorting algorithms. However, a slight modification-merely moving one recursive call inside an if statement- transforms ExpoSort into an astonishingly well-camouflaged variant of the classic InsertionSort with best- and worst-case running times of \u0398(n) and \u0398(n\n            <jats:sup>3<\/jats:sup>\n            ), respectively. This dual nature of\n            <jats:sc>ExpoSort<\/jats:sc>\n            serves as a reminder of the utmost care required when crafting pessimal algorithms, where a slight lapse in judgment could result in accidentally producing an embarrassingly practical algorithm.\n          <\/jats:p>","DOI":"10.1145\/3710795.3710805","type":"journal-article","created":{"date-parts":[[2024,12,27]],"date-time":"2024-12-27T23:18:59Z","timestamp":1735341539000},"page":"108-111","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["<scp>ExpoSort<\/scp>\n            : Breaking the quasi-polynomial-time barrier for reluctant sorting"],"prefix":"10.1145","volume":"55","author":[{"given":"Mikkel","family":"Abrahamsen","sequence":"first","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,12,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/358027.381121"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/990534.990536"},{"key":"e_1_2_1_3_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2022","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 4th Edition. MIT Press, 2022. isbn: 9780262046305.","edition":"4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540--72914--3_17"},{"key":"e_1_2_1_5_1","volume-title":"The Hacker's Dictionary","author":"Steele Guy","year":"1983","unstructured":"Guy Steele, Raphael Finkel, Don Woods, Mark Crispin, Richard M. Stallman, and Geoff Goodfellow. The Hacker's Dictionary. Harper & Row, 1983."}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3710795.3710805","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3710795.3710805","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:57:25Z","timestamp":1750298245000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3710795.3710805"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,27]]},"references-count":5,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,27]]}},"alternative-id":["10.1145\/3710795.3710805"],"URL":"https:\/\/doi.org\/10.1145\/3710795.3710805","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2024,12,27]]},"assertion":[{"value":"2024-12-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}