--- title: "Faster Sorting Algorithms Discovered Using Deep Reinforcement" description: "Tiny sorting routines for a handful of elements run an enormous number of times, because divide-and-conquer sorts… Cited by 24 papers here." authors: ["Daniel J. Mankowitz", "Andrea Michi", "Anton Zhernov"] year: 2023 venue: "Nature 618" source: "https://www.nature.com/articles/s41586-023-06004-9.pdf" licence: "CC BY 4.0" licence_url: "https://creativecommons.org/licenses/by/4.0/" summary_licence: "Elamur Cosmic License" canonical: "https://research.elamur.ai/free/en/papers/mankowitz-2023-faster-sorting-algorithms-discovered-deep/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/mankowitz-2023-faster-sorting-algorithms-discovered-deep/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2023](https://md.research.elamur.ai/free/en/papers/2023/page/4/) / Faster Sorting Algorithms Discovered Using Deep Reinforcement Learning # Faster Sorting Algorithms Discovered Using Deep Reinforcement Learning **Authors:** Daniel J. Mankowitz, [Andrea Michi](https://md.research.elamur.ai/free/en/authors/andrea-michi/) and Anton Zhernov · **Year:** 2023 · **Venue:** [Nature 618](https://md.research.elamur.ai/free/en/venues/nature/) ([Nature 2023](https://md.research.elamur.ai/free/en/venues/nature/2023/)) · **Publisher:** [Nature Portfolio](https://md.research.elamur.ai/free/en/publishers/nature-portfolio/) · **Licence:** [CC BY 4.0](https://creativecommons.org/licenses/by/4.0/) **Links:** [Publisher's page](https://doi.org/10.1038/s41586-023-06004-9) · [PDF](https://www.nature.com/articles/s41586-023-06004-9.pdf) · [OpenAlex](https://openalex.org/W4379739787) **Citations:** 175 citations (OpenAlex, 2026-10-14) · [24](https://md.research.elamur.ai/free/en/papers/mankowitz-2023-faster-sorting-algorithms-discovered-deep/cited-by/) in our library, of the 149,439 papers whose bibliographies we read ## Summary Tiny sorting routines for a handful of elements run an enormous number of times, because divide-and-conquer sorts call them on short subarrays. Decades of expert tuning have left little obvious room to speed them up. Mankowitz et al. (DeepMind) turn the search for such routines into AssemblyGame, a one-player game in which an agent builds a program by adding x86 assembly instructions (AT&T syntax) one at a time. The reward combines two parts. Correctness is checked by running the program on test inputs and comparing the results with the expected outputs. Efficiency is scored either by program length or by directly measured latency. The agent, AlphaDev, extends AlphaZero. A neural network guides MCTS, combining a Transformer encoder of the program with an encoder of the CPU register and memory state. Starting from scratch, AlphaDev found fixed and variable sorting routines that match or beat the best human-written versions in length and run faster in measured latency. Its sort 3, sort 4 and sort 5 routines are now part of the LLVM standard C++ library. This marks an RL-discovered component replacing hand-written code in widely used software. ## Key points - AlphaDev targets two kinds of small sort. Fixed sorts handle exactly n elements (sort 3/4/5). Variable sorts (VarSort3/4/5) accept any length up to n. - Measured latency is lower than the human baselines in every case: - VarSort3: 236,498 vs 246,040. - VarSort4: 279,339 vs 294,963. - VarSort5: 312,079 vs 331,198. - VarInt: 97,184 vs 295,358, roughly three times faster. - "Competitive": 75,973 vs 86,056. - All figures are the 5th percentile over 100 machines, with 95% confidence intervals. - AssemblyGame's search space is compared in size to chess (~10^120 games) and Go (~10^700). A single wrong instruction can make a whole program incorrect. - Compared with a stochastic-search baseline (AlphaDev-S), AlphaDev needs far fewer explored programs. AlphaDev-S fails from a cold start, and its warm-started version tends to get stuck in local optima once branching is involved. - The approach is also applied beyond sorting (e.g., VarInt and a competitive-programming task), suggesting it generalizes to other domains. *Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.* ## Institutions - [Google](https://md.research.elamur.ai/free/en/companies/google/) — Company, Mountain View, United States · 533 works · 443,884 citations - [Google DeepMind](https://md.research.elamur.ai/free/en/companies/google-deepmind/) — Company, London, United Kingdom · 82 works · 84,829 citations 📚 Shelves (3): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 19,503 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 18,805 works · [🗄️ Information Systems](https://md.research.elamur.ai/free/en/shelves/computer-science/information-systems/) · 1,888 works ## Cite Cite as: Daniel J. Mankowitz, Andrea Michi and Anton Zhernov. 2023. Faster Sorting Algorithms Discovered Using Deep Reinforcement Learning. Nature 618. The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @inproceedings{mankowitz2023faster, title = {{Faster Sorting Algorithms Discovered Using Deep Reinforcement Learning}}, author = {Daniel J. Mankowitz, Andrea Michi and Anton Zhernov}, booktitle = {Nature 618}, year = {2023}, doi = {10.1038/s41586-023-06004-9}, url = {https://doi.org/10.1038/s41586-023-06004-9} } ``` - [← previous A Survey of Safety and Trustworthiness of Large Language Models through the Lens of Verification and Validation](https://md.research.elamur.ai/free/en/papers/huang-2023-survey-safety-trustworthiness-large-language/) - [next → MiniGPT-v2: large language model as a unified interface for vision-language multi-task learning](https://md.research.elamur.ai/free/en/papers/chen-2023-minigpt-v2-large-language-model/) - [↑ back to papers of 2023](https://md.research.elamur.ai/free/en/papers/2023/page/4/) *Updated 3 November 2026*