Computer scientists improve Python sorting function – Tech Xplore
Click here to sign in with or
Forget Password?
Learn more
share this!
97
3
Share
Email
December 12, 2022
by University of Liverpool
University of Liverpool computer scientists have solved a long-standing algorithmic puzzle to speed up a core building block of Python, the most popular programming language and the foundation of modern artificial intelligence systems.
The discovery has resulted in a better solution to sorting lists in Python, called Powersort, that has been implemented in Python 3.11, the latest version released in October.
Powersort arranges lists of objects in ascending order by the “list.sort” and “sorted” functions and Dr. Sebastian Wild, Lecturer in the Department of Computer Science at the University of Liverpool, is responsible for its invention.
Dr. Wild had been studying TimSort, a custom sorting algorithm invented by Tim Peters, an influential Python developer, and specifically its merge policy, which determines the order in which detected runs are successively “merged” to form longer runs, until eventually the list is fully sorted.
Dr. Wild was surprised by how poorly understood its merge policy was as there had even been an algorithmic bug and potential security problem lurking associated with it. It turned out that this key component was later found to be flawed.
A discussion between Dr. Wild and his post doc supervisor at the time, Professor Ian Munro from University of Waterloo, Canada, found that a theoretical algorithm from the 1970s provided the optimal solution to the problem of finding good merging orders.
This discovery led to the birth of “Powersort,” which was originally published at the European Symposium on Algorithms 2018 and was further scrutinized by the Python community before it reached the Python reference implementation.
Dr. Wild said, “I am delighted that my research has been put to practical use and has been implemented in Python 3.11. I stumbled across the solution to finding good merging orders through my work investigating Timsort. A week after finding the 50 year old algorithm, ‘Powersort’ was born.”
“I’m very happy that Tim Peters himself took our idea into the CPython reference implementation. His Timsort implementation is a masterpiece of algorithm engineering, and nobody knows this code like he does.”
Carl Friedrich Bolz-Tereick, member of the Python Software Foundation and core developer of PyPy, an alternative implementation of Python added, “Powersort is a great example of how the open-source nature of Python allows us to very quickly bring cutting-edge research findings into production use for everyone. When I learned about Powersort, I could include it into PyPy in a matter of days.”
“With the official release of Python 3.11 this October, hundreds of millions of users will now enjoy sorting getting ever so slightly faster. Even though the improvement for many inputs is tiny, the sheer number of Python installations can lead to significant energy saving on a global scale.”
Timsort is also used in other important software platforms, including the Java and Android runtime libraries, used in most smartphones, and the V8 JavaScript engine used in Google Chrome and node.js, driving much of modern web applications which can all potentially profit from Powersort.
Dr. Wild continues to conduct research into sorting and he has just finished work on an improvement of Powersort, now merging four runs simultaneously in each step.
The study is published on the arXiv preprint server.
Explore further
Facebook
Twitter
Email
Feedback to editors
23 hours ago
0
Dec 9, 2022
1
Dec 9, 2022
0
Dec 8, 2022
1
Dec 8, 2022
0
15 hours ago
15 hours ago
15 hours ago
16 hours ago
16 hours ago
16 hours ago
19 hours ago
19 hours ago
20 hours ago
20 hours ago
Jun 17, 2022
Dec 11, 2018
Oct 7, 2019
Jul 30, 2020
Jul 1, 2021
Aug 18, 2022
20 hours ago
Dec 9, 2022
Dec 9, 2022
Dec 8, 2022
Dec 7, 2022
Dec 6, 2022
Use this form if you have come across a typo, inaccuracy or would like to send an edit request for the content on this page. For general inquiries, please use our contact form. For general feedback, use the public comments section below (please adhere to guidelines).
Please select the most appropriate category to facilitate processing of your request
Thank you for taking time to provide your feedback to the editors.
Your feedback is important to us. However, we do not guarantee individual replies due to the high volume of messages.
Your email address is used only to let the recipient know who sent the email. Neither your address nor the recipient’s address will be used for any other purpose. The information you enter will appear in your e-mail message and is not retained by Tech Xplore in any form.
Daily science news on research developments and the latest scientific innovations
Medical research advances and health news
The most comprehensive sci-tech news coverage on the web
This site uses cookies to assist with navigation, analyse your use of our services, collect data for ads personalisation and provide content from third parties. By using our site, you acknowledge that you have read and understand our Privacy Policy and Terms of Use.