Title: [RFC] Replace rust-timsort so RustPython sorting speed ~= CPython sorting speed · Issue #6093 · RustPython/RustPython · GitHub
Open Graph Title: [RFC] Replace rust-timsort so RustPython sorting speed ~= CPython sorting speed · Issue #6093 · RustPython/RustPython
X Title: [RFC] Replace rust-timsort so RustPython sorting speed ~= CPython sorting speed · Issue #6093 · RustPython/RustPython
Description: WIP/Draft PR Summary Replace the single usage of rust-timsort with a more performant sorting algorithm. Either Rust's default sorting algorithm or a crate like glidesort which has positive benchmarks against the default implementation. D...
Open Graph Description: WIP/Draft PR Summary Replace the single usage of rust-timsort with a more performant sorting algorithm. Either Rust's default sorting algorithm or a crate like glidesort which has positive benchmar...
X Description: WIP/Draft PR Summary Replace the single usage of rust-timsort with a more performant sorting algorithm. Either Rust's default sorting algorithm or a crate like glidesort which has positive benc...
Opengraph URL: https://github.com/RustPython/RustPython/issues/6093
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"[RFC] Replace rust-timsort so RustPython sorting speed ~= CPython sorting speed","articleBody":"[WIP/Draft PR](https://github.com/RustPython/RustPython/pull/6096)\n\n## Summary\n\nReplace the [single usage of rust-timsort](https://github.com/RustPython/RustPython/blob/a9a9e3bf118f6c631ef99fe7174215254f846097/vm/src/builtins/list.rs#L525-L528) with a more performant sorting algorithm. Either Rust's default sorting algorithm or a crate like [glidesort](https://crates.io/crates/glidesort) which has positive benchmarks against the default implementation.\n\n## Detailed Explanation\n\nAs of CPython 3.11, [Timsort is no longer the default sorting algorithm](https://www.wild-inter.net/posts/powersort-in-python-3.11). It is instead an algorithm called Powersort.\n\n### rust-timsort\n\nRustPython currently uses a forked project https://github.com/RustPython/rust-timsort as its default sorting algorithm. To quote rust-timsort's README.\n\n> This is still an extreme work-in-progress, and performance has vast room for improvement.\n\nThis performance gap has become noticeable as new unit tests in later Python versions are introduced, which attempt to sort larger and larger lists. Sorting 1 million random numbers with rust-timsort takes 10-20 minutes vs 0.3 seconds for CPython.\n\n```shell\nRustPython on statistics-module-kde-function [$!?] via :snake: v3.13.1 via :crab: v1.88.0 \n✦ ❯ time python -c \"from random import random; sorted([random() for i in range(1_000_000)]); print('DONE');\"\nDONE\n\nreal 0m0.309s\nuser 0m0.274s\nsys 0m0.036s\n\nRustPython on statistics-module-kde-function [$!?] via :snake: v3.13.1 via :crab: v1.88.0 \n✦ ❯ time cargo run --release -- -c \"from random import random; sorted([random() for i in range(1_000_000)]); print('DONE');\"\n Finished `release` profile [optimized] target(s) in 0.16s\n Running `target/release/rustpython -c 'from random import random; sorted([random() for i in range(1_000_000)]); print('\\''DONE'\\'');'`\nDONE\n\nreal 16m52.217s\nuser 16m51.926s\nsys 0m0.174s\n```\n\n### glidesort\n\n[Glidesort](https://crates.io/crates/glidesort) is a crate which contains a sorting algorithm Glidesort which is an apparent enhancement to Powersort. Unlike rust-timsort, Glidesort has posted benchmark numbers showing it comparing as good or significantly better (in the case of largely presorted lists) than Rust's builtin sorting method which is a Mergesort implementation.\n\n\u003cimg width=\"1325\" height=\"869\" alt=\"Image\" src=\"https://github.com/user-attachments/assets/b34bd341-0aad-4dc2-9d2c-b1aada0e2c05\" />\n\n## Drawbacks, Rationale, and Alternatives\n\n### Rationale\n\nCPython and PyPy both have left Timsort behind as better performing alternatives became available i.e. Powersort. I believe the usage of Timsort in any Python is an implementation detail and if better performing sorting algorithms are available, they should be fair game.\n\nIf we choose to go with the default Rust sort then an entire dependency is removed from RustPython and maintaining the sorting algorithm becomes a non-issue until such time as performance warrants using something different.\n\n### Drawbacks\n\n- A drawback with Glidesort is it does not seem to contain any tests and is not actively maintained. This would probably need forking like rust-timsort\n\n\n## Unresolved Questions\n\n- Is Rust's builtin sorting algorithm quick enough to be happy to drop dependencies on fancier algorithms for easier maintainability?\n- If not, is Glidesort not having tests and needing to be forked a blocker and should some other crates be considered?\n","author":{"url":"https://github.com/jackoconnordev","@type":"Person","name":"jackoconnordev"},"datePublished":"2025-08-13T22:39:22Z","url":"https://github.com/RustPython/RustPython/issues/6093"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:74182f8c-353a-c3fc-e615-e8b78ff8ac3f |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | ADD2:1F2B:12B65C0:18F2C49:6B01F721 |
| html-safe-nonce | d6f5450dcd514c9c2bd9c1eec2d076be242c5d08ffa74a293e362caba7c45a96 |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJBREQyOjFGMkI6MTJCNjVDMDoxOEYyQzQ5OjZCMDFGNzIxIiwidmlzaXRvcl9pZCI6IjQ0MDkwMjg4OTg4OTM5ODU1NzAiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ== |
| visitor-hmac | 9e76f6f530c89efdf42abb86088dce42242ae1b83226ab4cc75aa75a1181910f |
| hovercard-subject-tag | issue:3320091168 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/RustPython/RustPython/6093/issue_layout |
| twitter:image | https://opengraph.githubassets.com/106114e27bc328a2eabb9ac6594743b8c3f68f57148789e692fa6b0f2155e230/RustPython/RustPython/issues/6093 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/106114e27bc328a2eabb9ac6594743b8c3f68f57148789e692fa6b0f2155e230/RustPython/RustPython/issues/6093 |
| og:image:alt | WIP/Draft PR Summary Replace the single usage of rust-timsort with a more performant sorting algorithm. Either Rust's default sorting algorithm or a crate like glidesort which has positive benchmar... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | jackoconnordev |
| hostname | github.com |
| expected-hostname | github.com |
| None | 87e774ee7c6b3bee0490394e4d3e57ec9dbc956f74b87ea685dc8996c1676456 |
| turbo-cache-control | no-preview |
| go-import | github.com/RustPython/RustPython git https://github.com/RustPython/RustPython.git |
| octolytics-dimension-user_id | 39710557 |
| octolytics-dimension-user_login | RustPython |
| octolytics-dimension-repository_id | 135201145 |
| octolytics-dimension-repository_nwo | RustPython/RustPython |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 135201145 |
| octolytics-dimension-repository_network_root_nwo | RustPython/RustPython |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 423dbb54c5e7bfecc838eb387c1435eb3d0e760d |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width